1579. Remove Max Number of Edges to Keep Graph Fully Traversable
有一个无像图包含n个node
并且有3种边
TYPE1:只有ALICE可以通过
TYPE2:只有BOB可以通过
TYPE3:两个人都可以通过
edges告诉你有那些边:edges[i]=[type_i,u_i,v_i]
请问做多可以删掉几条边后，2个人还是可以从任意node抵达所有node
如果没办法则回传-1
思路:
照着hint的想法做下去
用union find
分别建立bob跟alice的并查表
(1)先把第三种type的边建立起来
(2)接着再去用其他两种边把没联通的点接起来
(1)、(2)都要记录用了几条边
最后检查两人的每个点是不是都有连通
没有就回传-1
有就回传所有边的数量-用掉的边
golang code :
func maxNumEdgesToRemove(n int, edges [][]int) int {
alice := make([]int, n+1)
bob := make([]int, n+1)
cnt := 0
for i := 1; i <= n; i++ {
alice[i] = i
bob[i] = i
}
for _, val := range edges {
if val[0] == 3 && find(val[1], &alice) != find(val[2], &alice) {
merge(val[1], val[2], &alice)
cnt++
}
}
for i := 1; i <= n; i++ {
bob[i] = alice[i]
}
for _, val := range edges {
if val[0] == 1 && find(val[1], &alice) != find(val[2], &alice) {
merge(val[1], val[2], &alice)
cnt++
}
if val[0] == 2 && find(val[1], &bob) != find(val[2], &bob) {
merge(val[1], val[2], &bob)
cnt++
}
}
for i := 1; i <= n; i++ {
if find(i, &bob) != 1 || find(i, &alice) != 1 {
return -1
}
}
return len(edges) - cnt
}
func find(node int, arr *[]int) int {
if node != (*arr)[node] {
(*arr)[node] = find((*arr)[node], arr)
}
return (*arr)[node]
}
func merge(a, b int, arr *[]int) {
parent1 := find(a, arr)
parent2 := find(b, arr)
if parent1 < parent2 {
(*arr)[parent2] = parent1
} else {
(*arr)[parent1] = parent2
}
}