推 aioiwer318: 別卷了 06/30 18:42
推 DJYOMIYAHINA: 剩我看到hard就躺平了 06/30 18:43
→ sustainer123: 我等等也來卷一下好了 06/30 18:49
→ CanIndulgeMe: 技術大神 06/30 18:52
→ oin1104: 別卷了 送我模型 06/30 18:52
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
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.82.160.103 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1719743887.A.159.html