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)