Is It A Tree?----poj1308

http://poj.org/problem?id=1308

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#define N 110
#define INF 0xfffffff
using namespace std;

int f[N],vis[N];

int Find(int x)
{
    if(x!=f[x])
        f[x]=Find(f[x]);
    return f[x];
}

int main()
{
    int a,b,t=1,pa,pb,flag,i,first;
    while(scanf("%d%d",&a,&b),a!=-1||b!=-1)
    {
        for(i=0;i<N;i++)
            f[i]=i;
        memset(vis,0,sizeof(vis));
        flag=0;
        if(a==0&&b==0)
        {
            printf("Case %d is a tree.
",t++);//空树也是树;
            continue;
        }
        vis[a] = vis[b] = 1;//说明此点出现过;
        first = a;
        if(a == b) flag = 1;
        pa = Find(a);
        pb = Find(b);
        if(pa != pb)
            f[pb] = pa;
        else
            flag = 1;
        while(scanf("%d%d", &a, &b), a+b)
        {
            vis[a] = vis[b] = 1;
            if(a == b) flag = 1;
            pa = Find(a);
            pb = Find(b);
            if(pa != pb)
                f[pb]=pa;
            else
            {
                flag=1;
            }
        }
        for(i=1; i<N; i++)
        {
            if(vis[i]==1 && Find(i) != Find(first))
            {
                flag=1;break;
            }
        }
        if(flag==1)
            printf("Case %d is not a tree.
",t++);
        else
            printf("Case %d is a tree.
",t++);
    }
    return 0;
}
原文地址:https://www.cnblogs.com/zhengguiping--9876/p/4677848.html