P191 Is It A Tree?

这样写case1不通过

#include <iostream>

using namespace std;

const int MAXN = 10000;
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] = 0;
        inDegree[i] = 0;
    }
}

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

bool isTree(){
    int count = 0; //集合数
    int root = 0;  //根结点数
    bool flag = true;
    for(int i = 0; i < MAXN; i++){
        if(!visit[i]){
            continue;
        }
        if(i == father[i]){
            count++;
        }
        if(inDegree[i] == 0){
            root++;
        }else if(inDegree[i] > 1){
            flag = false;
            break;
        }
    }
    if(count != 1 || root != 1){
        flag = false;
    }
    if(count == 0 && root == 0){ //空集也是树
        flag = true;
    }
    return flag;
}

int main(){
    int x, y;
    int t = 1;
    while(cin >> x >> y){
        if(x == -1 && y == -1) break;
        if(x == 0 && y == 0) {
            if(isTree()){
                printf("Case %d is a tree.\n", t++);
            }else{
                printf("Case %d is not a tree.\n", t++);
            }
            initial();
        }else{
            Union(x, y);
            visit[x] = true;
            visit[y] = true;
        }
    }
    return 0;
}

最后发现每次indegree[y]直接++是因为题中的两点有方向，前者指向后者
而之前的题目都是无方向。