深さ優先探索のテンプレ
AOJの深さ優先探索の入門的な問題を解いて、いちいち書くのが面倒と思ったのでテンプレ作ります(ほぼ使えないかもしれないが)
説明は下手です、すみません()
ちなみに、AOJの方のコードはこちら
AIZU ONLINE JUDGE: Code Review
#include<iostream> #include<vector> #include<string> #include<stack> #include<cstdio> #include<algorithm> #define WHITE 0 #define GRAY 1 #define BLACK 2 using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) int n, m[100][100] = { 0 }, nt[100] = { 0 };//ntはその頂点から他の頂点を探索するときに重ならないようにするための物 int color[100] = { WHITE }; int next(int u) { FOR(i, nt[u], n) { nt[u] = i + 1; if (m[u][i]==1){ return i;//もし何かつながる頂点があれば返す } } return -1;//なければ-1を返す } int dfs(int r) { stack<int>S; S.push(r); color[r] = GRAY; while (!S.empty()) { int u=S.top(); int v = next(u); if (v != -1) { if (color[v]==WHITE) { S.push(v); color[v] = GRAY; } } else { S.pop(); color[v] = BLACK; } } return 0; } int main() { cin >> n; REP(i, n) { int u, k; cin >>u >> k;// u--;// REP(j, k) { int muki; cin >> muki;// muki--; m[u][muki] = 1; } } REP(i, n) { if (color[i] == WHITE) { dfs(i); } } return 0; }
ちなみにGRAYとBLACKは分ける必要ないです
boolにした方が軽くなると思います
隣接リストを行列に直してやりましたが、遅いらしいのでこれはあまり使えないかもしれません()