ACM 615 Is It A Tree?
作法:很多
我採用暴力+BFS尋訪
我個人認為應該不用 不過我想不到別的方式 網友提供唄
/**我的做法不好**********************************************/
#include<stdio.h>
#include<stdlib.h>
main()
{
int n,m,time=1,a,b,c;
char map[20][20]={0},max=-1,min=100,flag[50]={0};
while(scanf("%d %d",&n,&m)==2&&n>=0&&m>=0)
{
if(n==0&&m==0)
{
printf("Case %d ",time++);
int find=0,no=0;
for(a=min;a<=max;a++) /*判定雙向的*/
{
if(flag[a]==0) continue;
for(b=min;b<=max;b++)
{
if(flag[b]==0) continue;
if(map[a][b]==1&&map[b][a]==1) no=1;
}
}
for(a=min;a<=max;a++) /*判定連結不超過1個*/
{
if(flag[a]==0) continue;
for(b=min;b<=max;b++)
{
if(flag[b]==0) continue;
if(map[a][b]==1) {find++;}
}
if(find>1) {no=1;break;}
find=0;
}
for(a=min;a<=max;a++) /*將所有路改成雙向*/
for(b=min;b<=max;b++)
if(map[a][b]==1) map[b][a]=1;
char queue[50]={0},flag2[50]={0},top=0;/*是否能探訪所有點 一顆樹!! 可能會產生2顆以上的樹*/
queue[0]=min;
for(a=0;a<=top;a++)
{
int nn=queue[a];
for(b=min;b<=max;b++)
if(map[nn][b]==1&&flag2[b]==0) {top++;queue[top]=b;flag2[b]=1;}
}
for(a=min;a<=max;a++)
if(flag[a]!=flag2[a]) {no=1;break;}
if(no==1) printf("is not a tree.\n");
else printf("is a tree.\n");
for(a=min;a<=max;a++)
for(b=min;b<=max;b++)
map[a][b]=0;
for(a=min;a<=max;a++) flag[a]=0;
max=-1;min=100;
}
else
{
if(n>max) max=n;
if(m>max) max=m;
if(n<min) min=n;
if(m<min) min=m;
flag[m]=1;flag[n]=1;
map[m][n]++;/*m連結到n*/
}
}
return 0;
}