684. 冗余连接

题目描述

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

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

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

示例 1：

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

示例 2：

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

提示:

n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ai < bi <= edges.length
ai != bi
edges 中无重复元素
给定的图是连通的

解法一：并查集

 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


type UnionFind struct {
    parent []int
}

func (uf *UnionFind) Init(n int) {
    uf.parent = make([]int, n)
    for i := 0; i < len(uf.parent); i++ {
        uf.parent[i] = i
    }
}

// Merge 合并包含 i 的集合和包含 j 的集合
// 返回 i 和 j 是否属于同一个集合
func (uf *UnionFind) Merge(i, j int) bool{
    iF, jF := uf.Find(i), uf.Find(j)
    if iF != jF {
        uf.parent[iF] = jF
        return false
    }
    return true
}

// Find 查询 i 的祖先（root）
func (uf *UnionFind) Find(i int) int {
    if uf.parent[i] != i {
        uf.parent[i] = uf.Find(uf.parent[i])
    }
    return uf.parent[i]
}

func findRedundantConnection(edges [][]int) []int {
    n := len(edges)
    uf := &UnionFind{}
    uf.Init(n+1)
    ansIdx := -1
    for i, edge := range edges {
        u, v := edge[0], edge[1]
        if uf.Merge(u, v) {
            ansIdx = i
        }
    }
    return edges[ansIdx]
}