LeetCode 1319. 连通网络的操作次数

Categories:

题目描述
思路分析
1. 解法一：并查集统计连通分量（推荐）
相似题目

题目描述

✅ 1319. 连通网络的操作次数

思路分析

解法一：并查集统计连通分量（推荐）

核心思路：

若边数少于 n - 1，无法连通，直接返回 -1。

使用并查集合并所有连接，统计连通分量数。

需要的操作数为 components - 1。

复杂度分析：

时间复杂度：O(n + m α(n))，其中 m 为边数。

空间复杂度：O(n)。

class Solution {
    public int makeConnected(int n, int[][] connections) {
        if (connections.length < n - 1) {
            return -1;
        }

        UnionFind uf = new UnionFind(n);
        for (int[] e : connections) {
            uf.union(e[0], e[1]);
        }
        return uf.count - 1;
    }

    static class UnionFind {
        int[] parent;
        int[] size;
        int count;

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

        int find(int x) {
            while (x != parent[x]) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }

        void union(int a, int b) {
            int ra = find(a);
            int rb = find(b);
            if (ra == rb) {
                return;
            }
            if (size[ra] < size[rb]) {
                int t = ra;
                ra = rb;
                rb = t;
            }
            parent[rb] = ra;
            size[ra] += size[rb];
            count--;
        }
    }
}

type UnionFind struct {
    parent []int
    size   []int
    count  int
}

func newUnionFind(n int) *UnionFind {
    parent := make([]int, n)
    size := make([]int, n)
    for i := 0; i < n; i++ {
        parent[i] = i
        size[i] = 1
    }
    return &UnionFind{parent: parent, size: size, count: n}
}

func (uf *UnionFind) find(x int) int {
    for x != uf.parent[x] {
        uf.parent[x] = uf.parent[uf.parent[x]]
        x = uf.parent[x]
    }
    return x
}

func (uf *UnionFind) union(a, b int) {
    ra := uf.find(a)
    rb := uf.find(b)
    if ra == rb {
        return
    }
    if uf.size[ra] < uf.size[rb] {
        ra, rb = rb, ra
    }
    uf.parent[rb] = ra
    uf.size[ra] += uf.size[rb]
    uf.count--
}

func makeConnected(n int, connections [][]int) int {
    if len(connections) < n-1 {
        return -1
    }

    uf := newUnionFind(n)
    for _, e := range connections {
        uf.union(e[0], e[1])
    }
    return uf.count - 1
}

相似题目

题目	难度	考察点
323. 无向图中连通分量的数目	中等	并查集
547. 省份数量	中等	并查集
261. 以图判树	中等	并查集
684. 冗余连接	中等	并查集
1579. 保证图可完全遍历	困难	并查集

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/82209747