aboutsummaryrefslogtreecommitdiff
path: root/remove_max_num_edge_traverse.py
diff options
context:
space:
mode:
Diffstat (limited to 'remove_max_num_edge_traverse.py')
-rw-r--r--remove_max_num_edge_traverse.py73
1 files changed, 73 insertions, 0 deletions
diff --git a/remove_max_num_edge_traverse.py b/remove_max_num_edge_traverse.py
new file mode 100644
index 0000000..3aee386
--- /dev/null
+++ b/remove_max_num_edge_traverse.py
@@ -0,0 +1,73 @@
+# 1579. Remove Max Number of Edges to Keep Graph Fully Traversable
+
+"""
+alice and bob have an undirected graph of 'n' nodes and three
+types of edges:
+type1: can be traversed by alice only
+type2: can be traversed by bob only
+type3: can be traversed by both alice and bob
+given an array of 'edges' where 'edges{i} = {typei, ui, vi}'
+repansents a bidirectional edge of type 'typei' between nodes
+'ui' and 'vi', find the maximum number of edges you can remove
+so that after removing the edges, the graph can still be fully
+traversed by alice and bob if starting from any node, they can
+reach all other nodes. return the maximum number of edges you
+can remove, or return -1 if alice and bob cannot traverse graph
+"""
+
+
+class Solution(object):
+ def maxNumEdgesToRemove(self, n, edges):
+ """
+ :type n: int
+ :type edges: List[List[int]]
+ :rtype: int
+ """
+ def find(i):
+ if i != root[i]:
+ root[i] = find(root[i])
+ return root[i]
+ def uni(x, y):
+ x, y = find(x), find(y)
+ if x == y:
+ return 0
+ root[x] = y
+ return 1
+ ans,e1,e2=0,0,0
+ root = range(n + 1)
+ for t, i, j in edges:
+ if t == 3:
+ if uni(i, j):
+ e1 += 1
+ e2 += 1
+ else:
+ ans += 1
+ root0 = root[:]
+ for t, i, j in edges:
+ if t == 1:
+ if uni(i, j):
+ e1 += 1
+ else:
+ ans += 1
+ root = root0
+ for t, i, j in edges:
+ if t == 2:
+ if uni(i, j):
+ e2 += 1
+ else:
+ ans += 1
+ return ans if e1 == e2 == n - 1 else -1
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.maxNumEdgesToRemove(
+ n=4,
+ edges=[[3, 1, 2], [3, 2, 3], [1, 1, 3], [1, 2, 4], [1, 1, 2], [2, 3, 4]],
+ )
+ )
+ print(
+ obj.maxNumEdgesToRemove(n=4, edges=[[3, 1, 2], [3, 2, 3], [1, 1, 4], [2, 1, 4]])
+ )
+ print(obj.maxNumEdgesToRemove(n=4, edges=[[3, 2, 3], [1, 1, 2], [2, 3, 4]]))