Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一个无向图,里面有三种边,1号边只能让Alice通过,2号边只能让Bob通过,3号边两人都可以走,问最多可以去掉图中几条边让两人可以走通所有节点,并查集应用
思路参考->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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理