题解 | #Is It A Tree?#

#include<stdbool.h>
#include <stdio.h>
const int maxnode = 10000;
int father[maxnode];
int indegree[maxnode];
bool vis[maxnode];
int height[maxnode];

void initial(int m){
    for(int i = 0; i < m; i++){
        father[i] = i;
        indegree[i] = 0;
        height[i] = 0;
        vis[i] = false;
    }
}

int Find(int x){
    if (x != father[x])
        father[x] = Find(father[x]);
    return father[x];
}
void Union(int a, int b){
    a = Find(a);
    b = Find(b);
    if(a != b){
        if (height[a] < height[b])
            father[a] = b;
        else if (height[a] > height[b])
            father[b] = a;
        else{
            father[b] = a;
            height[a]++;
        }
    }
}

bool istree(){
    int com=0;
    int root=0;
    bool flag = true;
    for (int i = 0; i < maxnode; i++){
        if (!vis[i])
            continue;
        if(i == father[i])
            com++;
        if(indegree[i] == 0)
            root++;
        else if (indegree[i] > 1)
            flag = false;
        if (com != 1 || root != 1)
            flag = false;
        if (com == 0 && root == 0)
            flag = true;
    }
    return flag;
}
int main() {
    int a, b, k = 0;
    initial(maxnode);
    while (scanf("%d %d", &a, &b) != EOF) { // 注意 while 处理多个 case
        // 64 位输出请用 printf("%lld") to 
        if(a == -1 && b == -1)
            break;
        if(a == 0 && b == 0){
            k+=1;
            if (istree())
                printf("Case %d is a tree.\n", k);
            else
                printf("Case %d is not a tree.\n", k);
            initial(maxnode);
        }
        else{
            Union(a, b);
            indegree[b]++;
            vis[a] = true;
            vis[b] = true;
        }
    }
    return 0;
}