複習樹的特性，只要符合下面敘述，我們就會稱這個圖為樹：

Ｏ->Ｏ->Ｏ （根邊點邊點）

• 圖上所有點是連通的，且沒有環，邊數是點數少一
• 有一個根，從根到圖上每個點，都只有唯一一種路徑

題目的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