题解 | Is It A Tree?

#include <bits/stdc++.h>
using namespace std;

const int MAXN=10000;

int father[MAXN];
int height[MAXN];

int inDegree[MAXN];
bool visit[MAXN];

void init(int n){
    for(int i=0;i<n;i++){
        father[i]=i;
        height[i]=0;
        inDegree[i]=0;
        visit[i]=false;
    }
}

int Find(int x){
    if(x!=father[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[x]=y;
        else if(height[y]<height[x]) father[y]=x;
        else {
            father[y]=x;
            height[x]++;
        }
    }
}

bool isTree(){
    bool flag=true;
    int component=0;
    int root=0;
    for(int i=0;i<MAXN;i++){
        if(!visit[i])continue;
        if(father[i]==i)component++;
        if(inDegree[i]==0)root++;
        else if(inDegree[i]>1)flag=false;
        if(component!=1||root!=1)flag=false;
        if(component==0&&root==0)flag=true;
        
    }
    return flag;
}

int main(){
    int x,y;
    int caseNum=0;
    init(MAXN);
    while(cin>>x>>y){
        if(x==-1&&y==-1)break;
        if(x==0,y==0){
            if(isTree())cout<<"Case "<<++caseNum<<" is a tree."<<endl;
            else cout<<"Case "<<++caseNum<<" is not a tree."<<endl;
            init(MAXN);
        }else {
            Union(x,y);
            inDegree[y]++;
            visit[x]=true;
            visit[y]=true;
        }
    }
}

本题难度在如何判断是否为树，判断树的条件非常简单，就是判断入度即可，我们可以把这些节点的入度都存储一下，入度为0的情况就是根节点，且可以根据入度大于1判断为非树结构，然后解释一下为什么要用visit，因为我们要生成一个唯一的树，不能是分裂的，所以必须在假如的节点中去查询，所以这里要进行标记，然后要注意一点，定义上允许空树为树，所以要写上这一点的特殊判断。