ALDS1-ALDS1_11_B Depth First Search（精選24）

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B&lang=ja

DFSの基本ということですが悩みながら実装しました。
再帰を使うとシンプルに実装できてよかったです。

どこで時間が加算されるのかが難しかったです。

提出コード

#include <bits/stdc++.h>
using namespace std;

static const int limit=110;

int n,u,v,t;
int d[limit];
int f[limit];
int visited[limit];
int k[limit];

vector<int>vec[limit];

void dfs(int x){
  if(visited[x]==1){
    return;
  }
  visited[x]=1;
  t++;
  d[x]=t;
  for(int i=0;i<k[x];i++){
    dfs(vec[x].at(i));
  }
  t++;  
  f[x]=t;

}


int main(){
  cin>>n;

  
  //入力
  for(int i=0;i<n;i++){  
    cin>>u>>k[i];
    u--;
    for(int j=0;j<k[i];j++){
      cin>>v;
      v--;
      vec[u].push_back(v); 
    }
  }
  for(int i=0;i<n;i++){
    if(visited[i]==0){
      dfs(i);
      f[i]=t;
    }
  }
  
  //出力
  
  for(int i=0;i<n;i++){
    cout<<i+1<<" "<<d[i]<<" "<<f[i]<<endl;
  }
  return 0;
}