Possible Bipartition — Bipartite Check BFS/DFS

Problem

n people; some pairs dislike each other. Can they be split into two groups with no two people who dislike each other in the same group?

Equivalent to: Is the dislikes graph bipartite?

Approach — BFS 2-Coloring

Try to 2-color the graph. If any edge connects same-colored nodes, not bipartite.

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

Solutions

Python

from collections import deque, defaultdict
class Solution:
    def possibleBipartition(self, n: int, dislikes: list[list[int]]) -> bool:
        adj=defaultdict(list)
        for u,v in dislikes: adj[u].append(v); adj[v].append(u)
        color={}
        for i in range(1,n+1):
            if i in color: continue
            q=deque([i]); color[i]=0
            while q:
                node=q.popleft()
                for nb in adj[node]:
                    if nb not in color: color[nb]=1-color[node]; q.append(nb)
                    elif color[nb]==color[node]: return False
        return True

C++

class Solution {
public:
    bool possibleBipartition(int n, vector<vector<int>>& dis){
        vector<vector<int>> adj(n+1); vector<int> col(n+1,-1);
        for(auto& d:dis){adj[d[0]].push_back(d[1]);adj[d[1]].push_back(d[0]);}
        for(int i=1;i<=n;i++){
            if(col[i]!=-1) continue;
            queue<int> q; q.push(i); col[i]=0;
            while(!q.empty()){
                int u=q.front();q.pop();
                for(int v:adj[u]){
                    if(col[v]==-1){col[v]=1-col[u];q.push(v);}
                    else if(col[v]==col[u]) return false;
                }
            }
        }
        return true;
    }
};

Complexity

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