cp/unionfind.cpp at master · prantoran/cp · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class UnionFind {
public:
    UnionFind(int sz) : root(sz), rank(sz), c(sz) {
        for (int i = 0; i < sz; i++) {
            root[i] = i;
            rank[i] = 1;
        }
    }

    int find(int x) {
        if (x == root[x]) {
            return x;
        }
        return root[x] = find(root[x]);
    }

    void unionSet(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                root[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                root[rootX] = rootY;
            } else {
                root[rootY] = rootX;
                rank[rootX] += 1;
            }

            c --;
        }
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }

    int components() { return c; }

private:
    vector<int> root;
    vector<int> rank;
    int c;
};


class UnionFind {
public:
    vector<int> rank, root;
    UnionFind(int n): rank(n, 1), root(n) {
        iota(root.begin(), root.end(), 0);
    }
    int find(int u) {
        return root[u] == u ? u : root[u] = find(root[u]);
    }
    bool unionSet(int u, int v) {
        int ru = find(x), rv = find(y);
        if (ru == rv) return false;
        if (rank[ru] > rank[rv]) {
            root[rv] = ru;
        } else if (rank[ru] < rank[rv]) {
            root[ru] = rv;
        } else {
            root[ru] = rv;
            root[rv] ++;
        }
        return true;
    }
    bool isConnected(int u, int v) {
        return find(u) == find(v);
    }
};