LeetCode-Solutions/Python/minimum-edge-toggles-on-a-tree.py at master · kamyu104/LeetCode-Solutions · GitHub

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
# Time:  O(n)
# Space: O(n)

# greedy, topological sort, bitmasks
class Solution(object):
    def minimumFlips(self, n, edges, start, target):
        """
        :type n: int
        :type edges: List[List[int]]
        :type start: str
        :type target: str
        :rtype: List[int]
        """
        diff = [1 if start[u] != target[u] else 0 for u in xrange(n)]
        if sum(diff)%2:
            return [-1]
        degree = [0]*n
        adj = [0]*n
        edge = [0]*n
        for idx, (u, v) in enumerate(edges):
            degree[u] += 1
            degree[v] += 1
            adj[u] ^= v
            adj[v] ^= u
            edge[u] ^= idx
            edge[v] ^= idx
        lookup = [False]*len(edges)
        for u in xrange(n):
            while degree[u] == 1:
                v, idx = adj[u], edge[u]
                degree[u] -= 1
                degree[v] -= 1
                adj[u] ^= v
                adj[v] ^= u
                edge[u] ^= idx
                edge[v] ^= idx
                if diff[u]:
                    diff[u] ^= 1
                    diff[v] ^= 1
                    lookup[idx] = True
                u = v
        return [i for i in xrange(len(lookup)) if lookup[i]]


# Time:  O(n)
# Space: O(n)
# greedy, topological sort
class Solution2(object):
    def minimumFlips(self, n, edges, start, target):
        """
        :type n: int
        :type edges: List[List[int]]
        :type start: str
        :type target: str
        :rtype: List[int]
        """
        def topological_sort():
            lookup = [False]*len(adj)
            q = [u for u in xrange(len(adj)) if degree[u] == 1]
            while q:
                new_q = []
                for u in q:
                    for v, idx in adj[u]:
                        if degree[v] == 0:
                            continue
                        degree[u] -= 1
                        degree[v] -= 1
                        if degree[v] == 1:
                            new_q.append(v)
                        if diff[u]:
                            diff[u] ^= 1
                            diff[v] ^= 1
                            lookup[idx] = True
                q = new_q
            return lookup

        diff = [1 if start[u] != target[u] else 0 for u in xrange(n)]
        if sum(diff)%2:
            return [-1]
        degree = [0]*n
        adj = [[] for _ in xrange(n)]
        for idx, (u, v) in enumerate(edges):
            degree[u] += 1
            degree[v] += 1
            adj[u].append((v, idx))
            adj[v].append((u, idx))
        lookup = topological_sort()
        return [i for i in xrange(len(lookup)) if lookup[i]]