树的判定条件

  • 单连通
  • 一个根节点（入度为0）
  • 无环（入度均不大于1或度数之和=结点数-1）
#include<iostream>
using namespace std;
const int maxn=10010;
int Father[maxn];
int height[maxn];
int indegree[maxn];//入度
bool visit[maxn];//使用的结点

void Initial(){
    for(int i=0;i<maxn;i++){
        Father[i]=i;
        height[i]=1;
        indegree[i]=0;
        visit[i]=false;
    }
    return ;
}
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)return;
    if(height[x]>height[y]){
        Father[y]=x;
    }
    else if(height[x]<height[y]){
        Father[x]=y;
    }
    else {
        Father[x]=y;
        height[y]++;
    }
    return;
}

bool istree(){
    int root=0;//根节点
    int sum=0;//连通分量
    for(int i=0;i<maxn;i++){
        if(!visit[i])continue;
        if(indegree[i]==0){
            root++;
            if(root>1)return false;//根节点不止一个
        }
        else if(indegree[i]>1)return false;//入度大于1
        if(Find(i)==i)sum++;
    }
    if(sum>1)return false;//连通分量大于1
    if(sum==1&&root!=1)return false;
    return true;
}

 int main(){
     int  n,m;
     int casenum=0;
     Initial();
     while(scanf("%d %d",&n,&m)!=EOF){
         if(n==-1&&m==-1)break;
         if(n==0&&m==0){
             if(istree())printf("Case %d is a tree.\n",++casenum);
             else printf("Case %d is not a tree.\n",++casenum);
             Initial();
         }
         
         else {
             Union(n,m);
             indegree[m]++;
             visit[n]=true;
             visit[m]=true;
         }
     }
     return 0;
 }