UVa -- 好用的資料結構 Disjoint Sets

為了解決 UVa 某些簡單題，刻一套自用的 disjoint-set forests 並不過分，

這裡採用 CLRS, Introduction to Algorithms 3/e 的程式碼，

以前念大學實在太混，這可是人生第一次實作 disjoint-set forests

((就算以前有作業，大概也是用抄的...))

struct DisjointSets {
    std::map<int, int> parent_;
    std::map<int, int> rank_;
    int size_;

    DisjointSets(int size) : size_(size) { 
        for (int i = 1; i <= size; i++) {
            parent_[i] = i;
            rank_[i] = 0;
        }
    }

    void Union(int x, int y) {
        Link(FindSet(x), FindSet(y));
    }

    void Link(int x, int y) {
        if (rank_[x] > rank_[y]) {
            parent_[y] = x;
        } 
        else {
            parent_[x] = y;
            if (rank_[x] == rank_[y]) {
                rank_[y]++;
            }
        }
    }

    int FindSet(int x) {
        if (x != parent_[x]) {
            parent_[x] = FindSet(parent_[x]);
        }
        return parent_[x];
    }
};

這是基本型，裡面用 std::map 說不定有 overkilled 之嫌。

以上 source code 可以再調，例如 Link() 可以先檢查 x == y，

如果一樣就不用傻傻的把 rank_[x]++

UVa 793

((AC: https://bitbucket.org/Menggen/uva/src/c70149a46f06089bbcdd0502468509e1f1e4975d/UVa/acm_793.cc?at=master))



當然 UVa Online Judge 不是吃素的，disjoint set 還可以稍加變化一下，

細節可參考：http://www.csie.ntnu.edu.tw/~u91029/DisjointSets.html

UVa 10608, 10685, 11503



此外，disjoint sets 也可取代使用 DFS 計算 component count，

哪個方便我們就用哪個。

UVa 10178

((提示：http://en.wikipedia.org/wiki/Euler_characteristic))

((當然不一定要這樣做))

((AC: https://bitbucket.org/Menggen/uva/src/56b804883cfe11520712b96eb0edac9699aa44d5/UVa/acm_10685.cc?at=master))