aboutsummaryrefslogtreecommitdiff
path: root/remove_max_num_edge_traverse.py
blob: 3aee386e14ce009abda1dee4bef7342c8f53c5ae (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
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]]))