※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「AOJ Problem Set from ALDS1 問30~34」の編集履歴(バックアップ)一覧に戻る

AOJ Problem Set from ALDS1 問30~34 - (2014/01/18 (土) 14:44:37) のソース

*Graph I - Graph
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_A
グラフのつながりを表示する問題。

 #include<stdio.h>
 #include<string.h>
 const int LIMIT=101;
 int g[LIMIT][LIMIT];
 
 
 int main(){
 	int n,u,k,v;
 	scanf("%d",&n);
 	memset(g,0,sizeof(g));
 	for(int i=0;i<n;i++){
 		scanf("%d %d",&u,&k);
  		while(k--){
 			scanf("%d",&v);
 			g[u][v]=1;
 		}
 	}
 	for(int i=1;i<=n;i++){
 		for(int j=1;j<=n;j++){
 			if(j>1)printf(" ");
 			printf("%d",g[i][j]);
  		}
 		printf("\n");
 	}
 }


*Graph I - Depth First Search
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B
グラフを探索した過程を出力する問題。
問題文の中の
深さ優先探索の過程において、訪問するための頂点(現在の頂点に隣接する頂点あるいは探索の始点)が複数ある場合は辞書式順序で選択する。
の一文に注意。

 #include<stdio.h>
 #include<string.h>
 
 const int LIMIT=101;
 int time=1;
 int g[LIMIT][LIMIT],d[LIMIT]={0},f[LIMIT]={0};
 int n;
  
 void search(int p){
 	if(d[p]>0)return ;
 	d[p]=time;
 	time++;
 	for(int i=1;i<=n;i++){
 		if(g[p][i]==1&&d[i]==0){
  			search(i);
 		}
 	}
 	f[p]=time;
 	time++;
 }
 
 int main(){
 	int u,k,v;
 	scanf("%d",&n);
 	memset(g,0,sizeof(g));
 	for(int i=0;i<n;i++){
 		scanf("%d %d",&u,&k);
  		while(k--){
 			scanf("%d",&v);
 			g[u][v]=1;
 		}
 	}
 	for(int i=1;i<=n;i++){
 		search(i);
 	}
 	for(int i=1;i<=n;i++)printf("%d %d %d\n",i,d[i],f[i]);
 }