LeetCode-684. 冗余连接 - sheep44044的小站

图论#

树可以看成是一个连通且无环的无向图。

给定一个图，该图从一棵 n 个节点 (节点值 1～n) 的树中添加一条边后获得。添加的边的两个不同顶点编号在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。

示例 1：

1
输入: edges = [[1,2], [1,3], [2,3]]
2
输出: [2,3]

示例 2：

1
输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
2
输出: [1,4]

并查集的方法

做了两题感觉比较公式🫤？

1
func findRedundantConnection(edges [][]int) []int {
2
    n := len(edges)
3

4
    parent := make([]int, n+1)
5
    for i := 1; i <= n; i++ {
6
        parent[i] = i
7
    }
8

9
    var find func(i int) int
10
    find = func(i int) int {
11
        if parent[i] != i {
12
            parent[i] = find(parent[i])
13
        }
14
        return parent[i]
15
    }
16

17
    for i := 0; i < n; i++ {
18
        a, b := edges[i][0], edges[i][1]
19
        rootA := find(a)
20
        rootB := find(b)
21
        if rootA == rootB {
22
            return edges[i]
23
        }else {
24
            parent[rootA] = rootB
25
        }
26
    }
27
    return nil
28
}