连通网格的操作次数

发表于
本文字数： 3.1k 阅读时长 ≈ 3 分钟

LeetCode题目，1319. Number of Operations to Make Network Connected

先看题目描述

sT2V3j.png

大意就是给定一个数字 n 代表有 n 个计算机，计算机的编号从 0 到 n - 1，connection 代表线缆，connection[i] = [a, b] 代表连接了计算机 a 和 b，我们可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。要我们计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1

算法和思路

并查集

这题本质上就是求给定的图中的连通分量的个数，返回的结果就是连通分量的个数 - 1，给定一个图求连通分量，可以使用并查集解决；当边的个数小于 n - 1 时，一定不能连通，直接返回 -1 即可

算法源码

下面是自己一开始的思路的源码，也是使用的并查集，但和用并查集求连通分量的思路不太一样，我的思路是既然 n 个点的最小生成树有 n - 1 条边，那么当碰到一条边，它的两个顶点已连通时，先看此时的边数是否大于 n - 1，若大于 n - 1，则将这条边舍弃，将边数减 1；若此时的边数等于 n - 1，那么为了使整个图连通，必须对这条边进行操作，将结果 加 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
class Solution {
    private int[] parent;

    public int makeConnected(int n, int[][] connections) {
        int ans = 0;
        int len = connections.length;
        if (len < n - 1) {
            return -1;
        }
        this.parent = new int[n];
        for (int i = 0; i < n; i++) {
            this.parent[i] = i;
        }
        for (int[] connection : connections) {
            int node1 = connection[0];
            int node2 = connection[1];
            if (union(node1, node2)) {
                continue;
            }
            if (len == n - 1) {
                ans++;
            } else {
                len--;
            }
        }
        return ans;
    }

    private int find(int x) {
        if (x != this.parent[x]) {
            this.parent[x] = find(this.parent[x]);
        }
        return this.parent[x];
    }

    private boolean union(int a, int b) {
        int x = find(a);
        int y = find(b);
        if (x == y) {
            return false;
        }
        this.parent[y] = x;
        return true;
    }
}

下面就是题解的代码，就是求图的连通分量的个数，然后返回连通分量的个数 - 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
57
58
59
60
61
class Solution {
    public int makeConnected(int n, int[][] connections) {
        if (connections.length < n - 1) {
            return -1;
        }

        UnionFind uf = new UnionFind(n);
        for (int[] conn : connections) {
            uf.unite(conn[0], conn[1]);
        }

        return uf.setCount - 1;
    }
}

// 并查集模板
class UnionFind {
    int[] parent;
    int[] size;
    int n;
    // 当前连通分量数目
    int setCount;

    public UnionFind(int n) {
        this.n = n;
        this.setCount = n;
        this.parent = new int[n];
        this.size = new int[n];
        Arrays.fill(size, 1);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }
    
    public int findset(int x) {
        return parent[x] == x ? x : (parent[x] = findset(parent[x]));
    }
    
    public boolean unite(int x, int y) {
        x = findset(x);
        y = findset(y);
        if (x == y) {
            return false;
        }
        if (size[x] < size[y]) {
            int temp = x;
            x = y;
            y = temp;
        }
        parent[y] = x;
        size[x] += size[y];
        --setCount;
        return true;
    }
    
    public boolean connected(int x, int y) {
        x = findset(x);
        y = findset(y);
        return x == y;
    }
}