「AOJ Problem Set from ALDS1 問30～34」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
*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 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;
}
