LeetCode-Solutions/Python/count-connected-subgraphs-with-even-node-sum.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
# Time:  O((n + e) * 2^n)
# Space: O(n + e)

# bitmask, dfs
class Solution(object):
    def evenSumSubgraphs(self, nums, edges):
        """
        :type nums: List[int]
        :type edges: List[List[int]]
        :rtype: int
        """
        def even(mask):
            def popcount(x):
                return bin(x).count('1')

            return not popcount(mask&odd_mask)%2

        def connected(mask):
            i = next(i for i in xrange(len(nums)) if mask&(1<<i))
            mask ^= 1<<i
            stk = [i]
            while stk:
                u = stk.pop()
                for v in adj[u]:
                    if not mask&(1<<v):
                        continue
                    mask ^= 1<<v
                    stk.append(v)
            return not mask

        adj = [[] for _ in xrange(len(nums))]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
        odd_mask = reduce(lambda accu, x: accu|(1<<x), (i for i in xrange(len(nums)) if nums[i]), 0)
        return sum(even(mask) and connected(mask) for mask in xrange(1, 1<<len(nums)))


# Time:  O((n + e) * 2^n)
# Space: O(n + e)
# bitmask, dfs
class Solution2(object):
    def evenSumSubgraphs(self, nums, edges):
        """
        :type nums: List[int]
        :type edges: List[List[int]]
        :rtype: int
        """
        def even(mask):
            parity = 0
            for i in xrange(len(nums)):
                if not mask&(1<<i):
                    continue
                parity ^= nums[i]
            return not parity

        def connected(mask):
            i = next(i for i in xrange(len(nums)) if mask&(1<<i))
            mask ^= 1<<i
            stk = [i]
            while stk:
                u = stk.pop()
                for v in adj[u]:
                    if not mask&(1<<v):
                        continue
                    mask ^= 1<<v
                    stk.append(v)
            return not mask

        adj = [[] for _ in xrange(len(nums))]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
        return sum(even(mask) and connected(mask) for mask in xrange(1, 1<<len(nums)))