题解 | #Is It A Tree?#

//树：
//入度除了根为0其他都为1
//只有一个根
//可以是空树 ：输入仅仅为0 0
//不能是环 1 1        1 2 2 1

#include <iostream>
#include <cstring>
using namespace std;

int height[10000];
int father[10000];
int indegree[10000];
bool visit[10000];//记录输入的结点编号

int Find(int x) {
    if (x == father[x])return x;
    else
        return Find(father[x]);
}


void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a != b) {
        if (height[a] > height[b])father[b] = a; //千万别写反了
        else if (height[a] < height[b])father[a] = b;
        else {
            father[b] = a;
            height[a]++;
        }
    }
}


int main() {
    int a, b;
    int number = 0; //第几组数据
    while (cin >> a >> b) {
        number++;
        memset(height, 0, sizeof(height));
        memset(father, 0, sizeof(father));
        memset(indegree, 0, sizeof(indegree));
        memset(visit, false, sizeof(visit));
        if (a == -1 && b == -1)break;


        if (a == 0 && b == 0)
            cout << "Case " << number << " is a tree." << endl;
        else if (a == b) {
            cout << "Case " << number << " is not a tree." << endl; // 排除掉单节点环
            while (1) {
                cin >> a >> b;
                if (a == 0 && b == 0)break;
            }
        } else {

            height[a] = 0;
            height[b] = 0;
            father[a] = a;
            father[b] = b;
            visit[a] = true;
            visit[b] = true;
            indegree[b]++;
            Union(a, b);

            while (1) {
                cin >> a >> b;
                if (a == 0 && b == 0)break;
                indegree[b]++;
                visit[a] = true;
                visit[b] = true;
                height[a] = 0;
                height[b] = 0;
                father[a] = a;
                father[b] = b;
                Union(a, b);

            }

            int root = 0;
            int root2=0;
            bool tree = true;
            for (int i = 1; i < 10000; i++) {
                if (visit[i] == true) {
                    if (indegree[i] > 1) {
                        tree = false;
                        break;
                    }
                    if (i == father[i]) {
                        root++;
                    }
                    if(indegree[i]==0){
                        root2++;
                    }
                }
            }

            //不能写>1，否则漏掉 1 2  2 1 这种多结点环
            //不能放在循环体内判断，否则root=0，会提前终止对所有visit的判断
            if (root != 1||root2!=1) { 
                tree = false;
            }
         
            if (tree == true)
                cout << "Case " << number << " is a tree." << endl;
            else
                cout << "Case " << number << " is not a tree." << endl;;
        }
    }
}