hdu1272

题意：判断给出的图是否为一棵树。

并查集的简单应用。

注意判断是否是一张空图。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int vis[maxn],fa[maxn];
int find(int x){
    if(x==fa[x])return x;
    return fa[x]=find(fa[x]);
}
int main(){
    int x,y;
    while(1){
        scanf("%d%d",&x,&y);
        if(x==-1&&y==-1)break;
        if(x==0&&y==0){
            puts("Yes");
            continue;
        }
        for(int i=1;i<=1e5;i++)
            vis[i]=0,fa[i]=i;
        fa[x]=y;
        vis[x]=vis[y]=1;
        int ans=0,flag=1,cnt=0;
        while(1){
            scanf("%d%d",&x,&y);
            if(x==0&&y==0)break;
            vis[x]=vis[y]=1;
            if(find(x)==find(y)){
                flag=0;
                continue;
            }
            fa[find(x)]=find(y);
            cnt++;
        }
        for(int i=1;i<=1e5;i++)
            if(vis[i]){
                ans=find(i);
                break;
            }
        for(int i=1;i<=1e5;i++)
            if(vis[i])flag&=(ans==find(i));
        printf(flag?"Yes
":"No
");
    }
    return 0;
}