b343 - 11518 - Dominos 2
題目描述
題目描述了骨牌倒塌的現象。給定骨牌的數量 n，骨牌之間的推倒關係 m，以及手動推倒的骨牌 l，要求計算最終倒下的骨牌總數。
解題思路
這題可以建模成一個有向圖，其中骨牌是節點，如果骨牌 x 倒下會推倒骨牌 y，則從 x 到 y 建立一條有向邊。然後，對於每個手動推倒的骨牌，執行深度優先搜尋 (DFS) 來遍歷所有可以被推倒的骨牌。使用一個 has 陣列來記錄已經訪問過的節點，避免重複計算。
複雜度分析
- 時間複雜度: O(n + m + l) 最壞情況下，DFS 需要遍歷所有節點和邊，且需要對每個手動推倒的骨牌執行一次 DFS。
- 空間複雜度: O(n)
e陣列儲存圖的鄰接表，has陣列用於記錄訪問過的節點，空間複雜度都與節點數量n成正比。
程式碼
#include <bits/stdc++.h>
using namespace std;
int n,m,l,ans,t,x,y;
vector <int> e[10005];
bool has[10005];
void dfs(int x){
if(has[x])return;
has[x]=1;
++ans;
for(int i=0;i<e[x].size();++i){
dfs(e[x][i]);
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
cin >> t;
for(int ca=1;ca<=t;++ca){
cin >> n >> m >> l;
ans=0;
memset(e,0,sizeof(e));
memset(has,0,sizeof(has));
for(int i=0;i<m;++i){
cin >> x >> y;
e[x].push_back(y);
}
for(int i=0;i<l;++i){
cin >> x;
dfs(x);
}
cout << ans << "\n";
}
}