ALDS_11_B - 深さ優先探索(精選24) 未了
DFSの基本ということですがまだ理解が追い付いていません。
もう少し勉強します。
考察
最初に訪問した時間とその頂点に戻ってきた時間を記録する,ということですが戻ってきた時間をどう記録してよいのか悩んでいます。
併せて隣接リストの書き方とかスタックの使い方などを復習しています。
書きかけのコード
#include <bits/stdc++.h> using namespace std; int d[110],f[110],seen[110]; int main(){ int n; cin>>n; vector<int>G[n]; int u,k,v; for(int i=0;i<n;i++){ cin>>u>>k; u--; for(int j=0;j<k;j++){ cin>>v; v--; G[u].push_back(v); } } stack<int>sta; sta.push(0); seen[0]=1; int time=1; while(sta.size() !=0){ int temp=sta.top(); sta.pop(); d[temp]=time; time++; for(int i=0;i<G[temp].size();i++){ int u=G[temp].at(i); if(seen[u] == 0){ sta.push(u); seen[u]=1; } } f[temp]=time; time++; } for(int i=0;i<n;i++){ cout<<i+1<<" "<<d[i]<<" "<<f[i]<<endl; } return 0; }