Leetcode|并查集+count|1319. 连通网络的操作次数_并查集 count

1 并查集 + count

class UnionFind {
public:
    int count;
    vector<int> parent, size;

    UnionFind(int n) {
        count = n;
        parent.resize(n);
        size.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    void unite(int a, int b) {
        int rootA = find_root(a);
        int rootB = find_root(b);
        if (rootA == rootB) return;
        if (size[rootA] < size[rootB]) {
            parent[rootA] = rootB;
            size[rootB] += size[rootA];
        } else {
            parent[rootB] = parent[rootA];
            size[rootA] += size[rootB];
        }
        count--;
    }

    bool connected(int a, int b) {
        int rootA = find_root(a);
        int rootB = find_root(b);
        return rootA == rootB;
    }

    int find_root(int node) {
        while (parent[node] != node) {
            parent[node] = parent[parent[node]];
            node = parent[node];
        }
        return node;
    }
};

class Solution {
public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        int num_edge = connections.size();
        if (num_edge < n - 1) return -1;
        UnionFind uf(n);
        for (int i = 0; i < num_edge; i++)
            uf.unite(connections[i][0], connections[i][1]);
        // 连通分量需要的最少边数 = 连通分量 - 1
        return uf.count - 1;
    }
};
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