UVa599 - The Forrest for the Trees(Disjoint Set)

題目大意：

給你很多個邊，這些邊透過節點的連接組成，接下來給你一些節點，要詢問這些節點有哪些節點有跟其他的節點做連結，哪些沒有。

有跟其他點做連結的點稱之為 tree，沒有的稱之為 acorns，請輸出他們的數量。

題目連結

觀念重點

• 並查集的應用
• 計算數量 acrons 與 tree 時的程式編寫
• 輸入的格式判斷

分析：

明顯可以看得出來這是一個 disjoint set 題目，哪裡可以看的出來呢？

在他說輸出 tree 與 acorns 時，不難發現 tree 就是有跟其他節點連結過的集合，acorns 就是沒有跟其他節點連結過的集合，透過 disjoint set 可以很快完美解決此問題。

如果還不懂 disjoint set 的可以看演算法知識 - Disjoint Set 並查集或Abdul Bari

tree and acrons 的程式碼編寫

一開始先開兩個陣列 cT and cA，cT 用來數 tree 的數量，cA 用來數 acorns。
並且在 disjoint set 建立時，先讓每個 cA[i]都設為 1，表示當前每個都是 acorns。

我們可以在每次的合併查詢中多寫一句話

• 如果代表元素不等於自己，那就讓 cA[i] 等於 0 且 cT[i] 為 1

接下來在到測資結束前，對題目想查詢的節點進行計數，如果 cA[i] = 1，等等輸出的 acorns 就加一，如果 cT[i] = 1，等等輸出的 tree 就加一

這樣可以方便又快速的解決此問題，這是我個人想到的，並不一定要用此方式解。

由於他詢問的節點不一定按照字母順序，記得要先用 vector 存起來。

記得對每一個要查詢的值進行判斷是 acorn or tree，再用 vector 紀錄，等等再進行計數。

我知道可能沒有寫得很乾淨，可以改進XD。

心得

這題讓我複習了很多 disjoint set，把我的小腦袋給弄醒了一些呀，好希望自己可以在學習的過程中更優秀、更努力，就可以讓自己變得更強，也透過寫演算法來增加我的思維。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 30 //題目最大數量
using namespace std;
int tree[MAXN], cT[MAXN], cA[MAXN]; //cntTree cntAcorn 判斷 i 是 tree or acorn
//tree 為 disjoint set 
int t;
string temp;
vector<int> record; //紀錄查詢的字元

void init(){ //初始
    for(int i = 0; i < MAXN; i++){ 
        tree[i] = i; //重設 disjoint set
        cA[i] = 1; //一開始每個節點都是 acorns
    }
    memset(cT, 0, sizeof(cT)); //一開始沒有節點是 tree
    record.clear(); //查詢字元紀錄刪除
}

int find_root(int i){ //disjoint set 查詢
    if(tree[i] != i)
        return tree[i] = find_root(tree[i]);
    return tree[i];
}

void debug(){ //debug 用，無意義
    for(int i = 0 ; i < MAXN; i++)
        cout << i << ' ';
    cout << '\n';
    for(int i = 0 ; i < MAXN; i++)
        cout << tree[i] << ' ';
    cout << '\n';
    for(int i = 0 ; i < MAXN; i++)
        cout << cA[i] << ' ';
    cout << '\n';
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    cin >> t;
    while(t--){
        init();
        while(cin >> temp){
            if(temp[0] == '('){ //合併節點
                int x, y, rx, ry; //rootx rooty
                x = temp[1] - 'A' + 1; //hash 用，透過 ascii
                y = temp[3] - 'A' + 1;
                rx = find_root(tree[x]); //找集合內代表元素
                ry = find_root(tree[y]); //找集合內代表元素
                if(rx != ry) //兩個不再同集和內就合併
                    tree[ry] = rx;
            }
            if(temp[0] == '*'){ //查詢節點
                cin >> temp;
                int root, x;
                for(int i = 0; i < temp.length(); i+=2){
                    x = temp[i] - 'A' + 1; //hash 用，透過 ascii
                    record.push_back(x); //紀錄查詢字元
                    root = find_root(tree[x]); //找集合內代表元素
                    //cout << root << ' ' << x << "\n";
                    if(root != x){ //如果集合內代表元素並不是 x 就表示他一定是 tree
                        cA[x] = 0; // 證明 x 不是 acorn
                        cA[root] = 0; //root 也不會是 acorn 因此設為 0
                        cT[root] = 1; //但 root 會 +1，因為有跟其他值連結
                    }
                }
                break;
            }
        }
        //debug();
        int sum_cT = 0, sum_cA = 0;
        for(int i = 0; i < record.size(); i++){ //計算 acorn and root 數量，透過記錄的查詢字元
            if(cT[record[i]]) sum_cT++; //表示 i 是 tree
            if(cA[record[i]]) sum_cA++; //表示 i 是 acorn
        }
        cout << "There are " << sum_cT << " tree(s) and " << sum_cA << " acorn(s).\n"; //輸出
    }

    return 0;
}