886. Possible Bipartition

Tags:

• Medium
• graph
• bfs
• recommend
• graph coloring

Link

Same as 785

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:

        Groups = {}

        arr = [ [] for i in range(n+1)]

        for a, b in dislikes:
            arr[a].append(b)
            arr[b].append(a)

        for i in range(1, n+1):
            if i not in Groups:
                Groups[i] = 1

            dq = deque([i])

            while dq:
                lens = len(dq)

                for _ in range(lens):
                    idx = dq.popleft()

                    for ii in arr[idx]:
                        if ii not in Groups:
                            Groups[ii] = -Groups[idx]
                            dq.append(ii)
                        elif Groups[ii] == Groups[idx]:
                            return False

        return True