給出一個無向圖，里面有三種邊，1號邊只能讓Alice通過，2號邊只能讓Bob通過，3號邊兩人都可以走，問最多可以去掉圖中幾條邊讓兩人可以走通所有節(jié)點，并查集應(yīng)用
思路參考->https://leetcode.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/solutions/3468567
1 #1579
2 #Runtime: 1874 ms (Beats 35.71%)
3 #Memory: 63.1 MB (Beats 71.43%)
4
5 class UnionFind:
6 def __init__(self, n):
7 self.parent = list(range(n + 1))
8 self.cc = n
9 def union(self, a, b):
10 fa = self.find(a)
11 fb = self.find(b)
12 if fa == fb:
13 return 0
14 self.parent[fa] = fb
15 self.cc -= 1
16 return 1
17
18 def find(self, a):
19 if self.parent[a] != a:
20 self.parent[a] = self.find(self.parent[a])
21 return self.parent[a]
22
23 def judge(self):
24 return self.cc == 1
25
26 class Solution(object):
27 def maxNumEdgesToRemove(self, n, edges):
28 """
29 :type n: int
30 :type edges: List[List[int]]
31 :rtype: int
32 """
33 alice, bob = UnionFind(n), UnionFind(n)
34
35 t = 0
36 for a, u, v in edges:
37 if a == 3:
38 t += alice.union(u, v) | bob.union(u, v)
39 if alice.judge() and bob.judge():
40 return len(edges) - t
41
42 for a, u, v in edges:
43 if a == 1:
44 t += alice.union(u, v)
45 elif a == 2:
46 t += bob.union(u, v)
47 if alice.judge() and bob.judge():
48 return len(edges) - t
49
50 if not alice.judge() or not bob.judge():
51 return -1
52
53 return len(edges) - t