这个题也太🐕了
0 0空集是树(没好好读题)
有环不是树(没想到)
其他并查集判断是否是一个连通图,如果是的话且没环就是树

#include<iostream>
#include<map>
#include<vector>
using namespace std;
const int maxn=10001;
int father[maxn];
int height[maxn];
int indegree[maxn];
bool flag=false;
map<int,int> mp;//记录点有没有出现过 
int index=0;
void init(){
    for(int i=0;i<maxn;i++){
        father[i]=-1;
        height[i]=0;
        indegree[i]=-1;
        mp.clear();
        flag=false;
    }
}
int find(int x){
    if(father[x]!=x)
        father[x]=find(father[x]);
    return father[x];    
}
void Union(int x,int y){
    x=find(x);
    y=find(y);
    if(x!=y){
        if(height[x]>height[y])
            father[y]=x;
        else if(height[y]>height[x])
            father[x]=y;
        else{
            father[x]=y;
            height[y]++;
        }
    }
}
void test(){
    int root=0;
    int sum=0;
    for(int i=0;i<maxn;i++){
        if(father[i]==i)
            sum++;
        if(indegree[i]==0)
            root++;
        if(indegree[i]>=2 || sum>=2){
            flag=true;
        }
    }
    if(sum!=0&&root==0)flag=true;
    if(flag)
        printf("Case %d is not a tree.\n",index);
    else
        printf("Case %d is a tree.\n",index);
}
int main(){
    int i,j;
    init();
    while(cin>>i>>j){
        if(i==0&&j==0){
            index++;
            test();
            init();
        }
        else if(i==-1&&j==-1){
            break;
        }
        else{
            if(mp.find(i)==mp.end()){
                mp[i]=1;
                father[i]=i;
                indegree[i]=0;
            }
            if(mp.find(j)==mp.end()){
                mp[j]=1; 
                father[j]=j;
                indegree[j]=0;
            }
            Union(i,j);
            if(i==j)flag=true;
            indegree[j]++;
        }
    }
    return 0;
}