AOJ Problem Set from ALDS1 問30～34 - c21coterie @ ウィキ

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

Graph I - Breadth First Search

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C
グラフを幅優先探索する問題。

#include<stdio.h>
#include<string.h>
#include<queue>

const int LIMIT=101;
int g[LIMIT][LIMIT],h[LIMIT];
 
int main(){
	int n,u,k,v;
	scanf("%d",&n);
 	memset(g,0,sizeof(g));
	memset(h,-1,sizeof(h));
	for(int i=0;i<n;i++){
		scanf("%d %d",&u,&k);
		while(k--){
			scanf("%d",&v);
			g[u][v]=1;
		}
	}
	std::queue<int> qu;
 	qu.push(1);
	h[1]=0;
while(qu.empty()==false){
		int p=qu.front();
		qu.pop();
		for(int i=1;i<=n;i++){
			if(g[p][i]==1&&h[i]==-1){
				h[i]=h[p]+1;
				qu.push(i);
			}
 		}
	}
	for(int i=1;i<=n;i++)printf("%d %d\n",i,h[i]);
}

Graph II - Minimum Spanning Tree

グラフの最小全域木の重みを求める問題。
何か効率が悪い方法を指定されていますが、指定の意図をくみ取って実装。

#include<stdio.h>
static const int MAX = 500;
static const int INFTY = (1<<21);

main(){
 int n, i, j, e, sum;
 int p[MAX],M[MAX][MAX];

 scanf("%d", &n);
 for ( i = 0; i< n; i++ ){
   p[i]=-1;
   for ( j = 0; j < n; j++ ){
     scanf("%d", &e);
     M[i][j] = (e==-1)?INFTY:e;
   }
 }
   for(int i=0;i<n;i++){
  	int p1,p2,g=INFTY;
	for(int nowP=1;nowP<n;nowP++){
		if(p[nowP]!=-1)continue;
 		for(int e=0;e<n;e++){
			if(M[nowP][e]<g && (p[e]!=-1 || e==0)){
				g=M[nowP][e];
				p1=nowP;
				p2=e;
			}
 		}
	}
	p[p1]=p2;
 }
 sum = 0;
 
 for ( i = 0; i < n; i++ ){
   if ( p[i] != -1 ) sum += M[i][p[i]];
 }
  
  printf("%d\n", sum);
  
  return 0;
}