LC-0886 Medium LeetCode

886. Possible Bipartition

Depth-First Search Breadth-First Search Union Find Graph

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 51% Topics: Depth-First Search, Breadth-First Search, Union Find, Graph

Reading material

Trees & Traversals 18 min Union–Find (DSU) 12 min Graphs 16 min

Reference solution (spoiler · python)

# Time:  O(|V| + |E|)
# Space: O(|V| + |E|)

import collections


class Solution(object):
    def possibleBipartition(self, N, dislikes):
        """
        :type N: int
        :type dislikes: List[List[int]]
        :rtype: bool
        """
        adj = [[] for _ in xrange(N)]
        for u, v in dislikes:
            adj[u-1].append(v-1)
            adj[v-1].append(u-1)

        color = [0]*N
        color[0] = 1
        q = collections.deque([0])
        while q:
            cur = q.popleft()
            for nei in adj[cur]:
                if color[nei] == color[cur]:
                    return False
                elif color[nei] == -color[cur]:
                    continue
                color[nei] = -color[cur]
                q.append(nei)
        return True

Solution from kamyu104/LeetCode-Solutions · MIT