前言
每天和你一起刷 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])
理解这三个操作，并查集就能使用的得心应手啦~
每天进步一点点，我们明天不见不散~
可以和我刷一辈子的每日一题吗？
一题一题，积累起来就是一辈子。
)
