You are given an undirected graph with n nodes as an adjacency list: graph[u] lists the neighbours of node u. Return true if the nodes can be split into two groups so that every edge connects a node in one group to a node in the other group. The graph may be disconnected.
{0, 2} and {1, 3} work.- 1 <= n <= 100
- 0 <= graph[u].length < n
- graph[u] has no self loops or duplicates
- If v is in graph[u], then u is in graph[v]
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force tries all 2^n ways of splitting the nodes, which is hopeless. The key fact: once you pick a colour for one node, the colours of its whole component are forced, because every neighbour must take the opposite colour. So just colour greedily with BFS: give the start node colour 0, its neighbours colour 1, their neighbours colour 0, and so on. A conflict (an edge whose ends share a colour) means there is an odd cycle and the graph is not bipartite.
Algorithm
- Make a
colorarray filled with -1 (uncoloured). - For every node that is still uncoloured, colour it 0 and push it into a queue.
- Pop a node; for each neighbour, if uncoloured give it the opposite colour and push it.
- If a neighbour already has the same colour as the node, return
false. - If every component finishes without conflict, return
true.
O(V + E)Space: O(V)class Solution: def isBipartite(self, graph: List[List[int]]) -> bool: n = len(graph) color = [-1] * n for s in range(n): if color[s] != -1: continue color[s] = 0 q = deque([s]) while q: u = q.popleft() for v in graph[u]: if color[v] == -1: color[v] = 1 - color[u] q.append(v) elif color[v] == color[u]: return False # both ends share a colour return True