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

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

AOJ Problem Set from ALDS1 問30~34 - (2014/01/18 (土) 14:44:37) の1つ前との変更点

追加された行は青色になります

削除された行は赤色になります。

 *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]);
  }