ALDS_1_11_B Depth First Search

問題
深さ優先探索 | アルゴリズムとデータ構造 | Aizu Online Judge

今日はALDSの復習です。深さ優先探索の実装です。超基本問題ですね。
深さ優先探索⇔スタック、幅優先探索⇔キューって対応しています。なのでスタックを用いて実装することも可能ですが、面倒です。
初めて解いた時はスタックでやろうとして、よくわからず解けなかったのですが、久しぶりに再帰で書いてみたら割とすんなりできました。

#include<stdio.h>
#define MAX 100

int adj[MAX][MAX];/*隣接行列*/
int d[MAX];/*発見時刻*/
int f[MAX];/*終了時刻*/
int flg[MAX];/*ノード訪問したかどうか*/
int time=0;

void dfs(int u,int n){
	
	flg[u]=1;
	d[u]=++time;
	
	for(int i=0;i<n;i++){
		if(adj[u][i] && !flg[i]){/*ノードuから到達可能かつ未訪問*/
			dfs(i,n);
		}
	}
	f[u]=++time;
	
	return;
	
}

int main(){
	int n,i,j;
	int x,y,z;
	
	scanf("%d",&n);
	
	for(i=0;i<n;i++){
		flg[i]=0;
		for(j=0;j<n;j++)
			adj[i][j]=0;
	}
	
	for(i=0;i<n;i++){
		scanf("%d %d",&x,&y);
		for(j=0;j<y;j++){
			scanf("%d",&z);
			adj[x-1][z-1]=1;
		}
	}
	
	for(i=0;i<n;i++)
		if(!flg[i])
			dfs(i,n);
	
	
	for(i=0;i<n;i++)
		printf("%d %d %d\n",i+1,d[i],f[i]);
	
	return 0;
	
}

スタート（1番のノード）から到達できないノードがあるので

	for(i=0;i<n;i++)
		if(!flg[i])
			dfs(i,n);

こんな感じで対応しました。

以前解けなかった問題がすんなり解けるのは非常に嬉しいです。