Problem statement

https://binarysearch.com/problems/Separate-People-Given-Dislike-Relations/

Solution

Variation of Leetcode 0785. Is Graph Bipartite.

Complexity

Time is O(V + E), space is O(E + V) as well.

Code

class Solution:
    def solve(self, n, enemies):
        def dfs(start):
            for neib in G[start]:
                if dist[neib] >= 0 and dist[neib] == dist[start]:
                    self.loop = True
                elif dist[neib] < 0:
                    dist[neib] = dist[start]^1
                    dfs(neib)
            
        self.loop, dist = False, [-1] *(n)
        G = defaultdict(list)
        for x, y in enemies:
            G[x] += [y]
            G[y] += [x]
        
        for i in range(n):
            if self.loop: return False
            if dist[i] == -1:
                dist[i] = 0
                dfs(i)
                
        return True