d279 - 00280 - Vertex
題目描述
題目要求對於一個給定的有向圖和一個起始節點，找出所有從該起始節點無法到達的節點。輸入包含多個有向圖，每個圖的節點數和邊的資訊，以及多個查詢起始節點。
解題思路
使用深度優先搜尋 (DFS) 演算法來遍歷圖。對於每個查詢的起始節點，從該節點開始進行 DFS，並標記所有可到達的節點。然後，遍歷所有節點，找出未被標記的節點，這些節點就是無法從起始節點到達的節點。
複雜度分析
- 時間複雜度: O(N^2 + M * Q)，其中 N 是節點數，M 是邊數，Q 是查詢次數。最壞情況下，DFS 需要遍歷所有節點和邊，並且對於每個查詢，都需要進行一次 DFS。
- 空間複雜度: O(N)，主要用於儲存圖的鄰接矩陣
a和標記節點是否可到達的陣列ans。
程式碼
#include <iostream>
using namespace std;
int n,m,a[1001][1001],r,ans[1001],total;
void dfs(int x){
for(int i=1;i<=n;++i){
if(a[x][i]&&ans[i]==0){
ans[i]=1;
++total;
dfs(i);
}
}
}
int main(){
while(cin >> n){
if(n==0)break;
for(int i=1;i<=n;++i){
ans[i]=0;
for(int j=1;j<=n;++j)
a[i][j]=0;
}
while(cin >> m){
if(m==0)break;
while(cin >> r){
if(r==0)break;
a[m][r]=1;
}
}
cin >> m;
for(int i=0;i<m;++i){
for(int j=1;j<=n;++j)
ans[j]=0;
total=0;
cin >> r;
dfs(r);
cout << n-total;
for(int j=1;j<=n;++j)
if(ans[j]==0)
cout << " " << j;
cout << '\n';
}
}
}