題目大意
給你幾個(gè)點(diǎn)的連接情況吴侦，問你這些點(diǎn)能否連接成一棵樹咧栗。
思路
連接成一棵樹的條件有(1)不能有環(huán)(2)只有一個(gè)根節(jié)點(diǎn)飘诗，不然就是森林了圆丹。
那么我們其實(shí)只要用并查集依次把那些點(diǎn)連接起來，再通過連接兩個(gè)點(diǎn)判斷其是否有同一個(gè)根節(jié)點(diǎn)虫给，如果有的話藤抡，那么就會(huì)形成環(huán)狀回路，肯定不行抹估。
在連接完成之后再去判斷所有的結(jié)點(diǎn)中根節(jié)點(diǎn)的個(gè)數(shù)缠黍，如果個(gè)數(shù)不止一個(gè)，那就是森林了药蜻，就不是一棵樹了瓷式，肯定也不行啦。
當(dāng)然還有一點(diǎn)要注意空樹也是樹语泽。
代碼如下：
#include<stdio.h>
#include<string.h>
int pre[1005];
int find(int x)
{
while(pre[x]!=x)
{
x=pre[x];
}
return x;
}
int mix(int x,int y)
{
int fx=find(x),fy=find(y);
if(fx!=fy)
{
pre[fy]=fx;
}
}
int main()
{
int cnt=1,a,b,flag;
while(1)
{
flag=0;
while(~scanf("%d%d",&a,&b)&&a&&b)
{
if(a==-1&&a==-1)return 0;
if(pre[a]==0)pre[a]=a;
if(pre[b]==0)pre[b]=b;
if(find(a)==find(b))flag=1;
if(flag!=1)
{
mix(a,b);
}
}
int sum=0;
for(int i=1;i<=1005;i++)
{
if(pre[i]==i) sum++;
pre[i]=0;
}
if(sum>1||flag==1)printf("Case %d is not a tree.\n",cnt++);
else printf("Case %d is a tree.\n",cnt++);
}
return 0;
}
