UVa280 - Vertex(DFS)

題目大意：

給你一張單向圖，寫一個程式，我們想詢問從 x 點進行搜尋會有哪些點是不會被搜尋到。

題目測資有點小麻煩，需要處理。

分析：

標準的 DFS，基本上沒有難度的，需要注意的是要輸出的節點是未經過，所以要記錄下來。

需要特別注意的是一開始的點並不會被當作有經過，所以一開始的點不能被視為 visit。

心得

這應該是我覺得最簡單的題目之一，寫得好開心。

題目程式碼

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 200
using namespace std;
int visit[MAXN] , graph[MAXN][MAXN] ;
int n , len , sz , temp_n , temp_i ;
vector<int> record ;

void dfs(int x ){
    for(int i = 1 ; i <= n ; i++ ){
        //cout << x << ' ' << i << ' ' << graph[x][i] << '\n' ;
        if(graph[x][i] && !visit[i]){
            visit[i] = 1 ;
            dfs(i);
        }
    }
}

int main(){
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
    freopen("out.txt" , "w" , stdout );
#endif // LOCAL

    while(cin >> n && n ){
        memset(graph,0,sizeof(graph));
        while(cin >> temp_i && temp_i )
            while(cin >> temp_n && temp_n) graph[temp_i][temp_n] = 1 ;

        cin >> len ;
        for(int i = 0 ; i < len ; i++){
            cin >> temp_n ;
            sz = 0 ;
            record.clear();
            memset(visit,0,sizeof(visit));
            dfs(temp_n);
            for(int j = 1 ; j <= n ; j++){
                if(!visit[j])
                    record.push_back(j);
            }
            cout << record.size() ;
            for(auto it : record )
                cout << ' ' << it ;
            cout << '\n' ;
        }
    }

}