题解 | #Is It A Tree?#

树：

要求1：每个节点入度<=1;

要求2：(连通分量=1&&根=1)||(连通分量=0&&根=0)

#include <iostream>

using namespace std;

const int maxn=100010;
int father[maxn];
int height[maxn];
int indegree[maxn];
int visit[maxn];

//初始化
void initial(){
    for(int i=0;i<=maxn;i++){
        father[i]=-1;
        height[i]=0;
        indegree[i]=0;
        visit[i]=0;
    }
}

//Find
int Find(int x){
    if (father[x]==-1)return x;
    return Find(father[x]);
}

//union
void Union(int x,int y){
    int fx=Find(x);
    int fy=Find(y);
    if (fx==fy)return;
    if(height[fx]>height[fy]){
        father[fy]=fx;
    }
    else if(height[fx]<height[fy]){
        father[fx]=fy;
    }
    else{
        father[fx]=fy;
        height[fy]++;
    }
}

int istree(){
    //每一个节点入度<=1，（根节点数=1，连通分量数=1||空）
    int flag=1;
    int component=0;
    int root=0;
    for(int i=0;i<maxn;i++){
        if(!visit[i])continue;
        if(father[i]==-1)component++;//连通分量数
        if(indegree[i]==0)root++;//根节点数
        if(indegree[i]>1)flag=0;
    }
    if(component!=1||root!=1)flag=0;
    if(component==0&&root==0)flag= 1;
    return flag;

}



int main()
{
    int n;
    int m;
    int para1,para2;
    int cases=1;
    initial();
    while(cin>>para1>>para2){
        if(para1==-1||para2==-1)return 0;
        else if(para1==0||para2==0){
            //cout<<"para1:"<<para1<<endl;
            if(istree())printf("Case %d is a tree.\n",cases++);
            else printf("Case %d is not a tree.\n",cases++);
            initial();
        }
        else{
            Union(para1,para2);
            //cout<<"u"<<endl;
            visit[para1]=1;
            visit[para2]=1;
            indegree[para2]++;
        }
    }
    return 0;
}