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

This is classical graph theory problem: you have graph, and you need to check if it can be bipartitioned: all nodes must be divided into two groups, such that there is not connections between nodes in each group.

Classical way to solve this problem is any graph traversal algorighm, here I chose dfs. The variable self.adj_list is adjacency list of our graph, for example if we have connections [[1,2],[2,3],[3,4],[4,5],[1,5]], then it is equal to 1:{2,5}; 2:{1,3}, 3:{4,2}, 4:{3,5}, 5:{1,4} I also have self.found_loop variable to terminate early if we found loop with odd length, which is sufficient and necessary condition that graph can not be bipartitioned, for example in our case we have 1->2->3->4->5->1 the loop with size 5.

When we traverse nodes, we evaluate their distances (in my code list self.dist) from the starting point, and if in some moment node is already visited and its parity is broken, than we found odd loop.

Note also, that original graph is not necessarily connected, and we need to start our dfs from all nodes to make sure that we traverse all graph.

Complexity We traverse every connection between nodes only once, so we have classical O(E+V) time complexity, where E is number of edges and V is number of vertices (V = N in our case and V = len(dislikes)). Space complexity is also O(E+V), because we keep adjacency list for all our nodes and colors

class Solution:
    def dfs(self, start):
        if self.found_loop == 1: return        #early stop if we found odd cycle
    
        for neib in self.adj_list[start]:
            if self.dist[neib] > 0 and (self.dist[neib] - self.dist[start]) %2 == 0:
                self.found_loop = 1
            elif self.dist[neib] < 0:  #not visited yet
                self.dist[neib] = self.dist[start] + 1
                self.dfs(neib)
            
    def possibleBipartition(self, N, dislikes):
        self.adj_list = defaultdict(list)
        self.found_loop, self.dist = 0, [-1] *(N+1)
        
        for i,j in dislikes:
            self.adj_list[i].append(j)
            self.adj_list[j].append(i)
        
        for i in range(N):
            if self.found_loop: return False    #early stop if we found odd cycle
            
            if self.dist[i] == -1:    #not visited yet
                self.dist[i] = 0
                self.dfs(i)
        
        return True

If you like the solution, you can upvote it on leetcode discussion section: Problem 0886