684. 冗余连接

力扣刷题记录

图论 加边法 并查集

684. 冗余连接

思路

遍历每一条边，看是否出现环路即可，如果出现了环路，则表明这个边是多余的，直接返回即可

这个思路跟Kruskal 算法(加边法)，最小生成树很像，其中也有一个过程并查集判断是否存在回路，因此新建parent数组表示并查集，遍历每一条边，查两个点的父元素，如果不相同，说明没有形成环路，更新parent数组，做一个并集的操作
反之相同说明已经存在环路直接返回即可

代码

func findParent(parent []int, x int) int{for parent[x] > 0{x = parent[x]}return x
}func findRedundantConnection(edges [][]int) []int {// 克鲁斯卡尔算法 加边法 关键是如何判断回路 并查集parent := make([]int, len(edges) + 1)for _, val := range edges{m := findParent(parent, val[0])n := findParent(parent, val[1])if m != n{// 父元素不相同 可以选择parent[m] = n}else{return val}}return nil
}

时间复杂度：O(n * log n)
空间复杂度：O(n)