Leetcode 922 Solution

This article provides solution to leetcode question 922 (possible-bipartition)
Categories:
Tags:
Access this page by simply typing in "lcs 922" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/possible-bipartition

Solution

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        edges = collections.defaultdict(list)
        for src, dst in dislikes:
            edges[src].append(dst)
            edges[dst].append(src)



        colors = {}
        def dfs(node, color):
            if node in colors:
                return colors[node] == color
            colors[node] = color
            return all(dfs(nei, color ^ 1) for nei in edges[node])



        nodes = list(edges.keys())
        return all(dfs(node, 0) for node in nodes if node not in colors)