diff options
Diffstat (limited to 'remove_max_num_edge_traverse.py')
-rw-r--r-- | remove_max_num_edge_traverse.py | 73 |
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]])) |