【LeetCode】每日一题 2024_10_27 冗余连接（并查集）

前言

每天和你一起刷 LeetCode 每日一题~

今年过去 300 天了呀

LeetCode 启动！

题目：冗余连接

代码与解题思路

题目翻译：找到一条边删除之后，所有节点依旧是连通的

看到连通块，就不由自主的先把并查集的思路套进去，看看能不能实现

核心思路：

用并查集将边一个个链接起来，当有边和连通块重复链接的时候，就证明这条边是可以删除的，将其删除即可，代码如下：

func findRedundantConnection(edges [][]int) []int {
    n := len(edges)
    p := make([]int, n+1)
    for i := 1; i <= n; i++ {
        p[i] = i
    }
    // 并查集模版
    var find func(int) int 
    find = func(x int) int {
        if p[x] != x {
            p[x] = find(p[x])
        }
        return p[x]
    }
    for i := 0; ; i++ {
        // 如果联通两次，证明这条边可以删除，返回即可
        if find(edges[i][0]) == find(edges[i][1]) {
            return edges[i]
        }
        // 链接这两条边
        p[find(edges[i][0])] = find(edges[i][1])
    }
}

如果不了解并查集，推荐阅读：我之前写的并查集模版介绍

这里讲一讲并查集几个核心的操作：

1、并查集模版

find 操作：求 x 集合的编号（也就是求 x 的祖先节点）

var find func(int) int 
find = func(x int) int {
    if p[x] != x {
        p[x] = find(p[x])
    }
    return p[x]
}

2、p 数组初始化

在使用 p 数组前，需要进行的初始化，将节点存入 p 数组中（节点编号从 1 开始）

p := make([]int, n+1)
for i := 1; i <= n; i++ {
    p[i] = i
}

3、合并联通块

p[find(edges[i][0])] = find(edges[i][1])

理解这三个操作，并查集就能使用的得心应手啦~

每天进步一点点，我们明天不见不散~

可以和我刷一辈子的每日一题吗？
一题一题，积累起来就是一辈子。