Graph-Tree: uva 615 Is It A Tree?

复习树的特性，只要符合下面叙述，我们就会称这个图为树：

Ｏ->Ｏ->Ｏ （根边点边点）

• 图上所有点是连通的，且没有环，边数是点数少一
• 有一个根，从根到图上每个点，都只有唯一一种路径

题目的Input是

the first integer identifies the node from which the edge begins
the second integer identifies the node to which the edge is directed.

两相隔的数字是点边点的关系，每个case来的时候，会一直塞点边点，直到0 0出现。
终止input是-1 -1

思路：

判断是否有环，除了用adj矩阵配遍历搜寻，还可以用并查集。
用并查集的话，速度比较快，但是输入数字范围只有说大於0，最後找了参考，知道要100000才过。

程序码：

#include <iostream>
#define N 100000

using namespace std;

int used[N];
int arr[N];

int getroot(int);

int main() {
    int u, v, num = 1;
    
    while(cin >> u >> v) {
        if (u<0 || v<0) break;
        int isTree = 1;
        for (int i = 0; i < N; ++i) {
            arr[i] = i;
            used[i] = 0;
        }
        
        while(u!=0 && v!=0) {
            if (getroot(u) == getroot(v))
                isTree = 0;
            if (isTree) {
                used[u] = used[v] = 1;
                arr[getroot(v)] = getroot(u);
            }
            cin >> u >> v;
        }
        
        if (isTree){
            int flag = 0;
            for(int i = 0; i < N; ++i) {
                if (used[i] && getroot(i) == i) {
                    if (flag) {
                        isTree = 0;
                        break;
                    }
                    flag = 1;
                }
            }
        }
        
        if (isTree)
            cout << "Case " << num << " is a tree." << endl;
        else
            cout << "Case " << num << " is not a tree." << endl;
        num++;
    }

    return 0;
}

int getroot(int v) {
    if (arr[v]!=v){
        arr[v] = getroot(arr[v]);
    }
    return arr[v];
}

参考：
https://web.ntnu.edu.tw/~algo/Tree.html
https://blog.csdn.net/mobius_strip/article/details/39782475