Practice › Graphs
Is Graph Bipartite
Medium · Graphs · Asked at Meta, Amazon, Google, Microsoft
Can the nodes be split into two groups so that every edge joins nodes from different groups? The graph may be disconnected. Print YES or NO.
Input
First line: n m. Next m lines: u v — an undirected edge (nodes are 1..n).
Output
YES or NO.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ m ≤ 2 · 10^5
Two-color each component with BFS: neighbours get the opposite color. An edge between equal colors means NO (an odd cycle).
Example 1
Input
4 4 1 2 2 3 3 4 4 1
Output
YES
Example 2
Input
3 3 1 2 2 3 3 1
Output
NO
Hints
- Try to 2-color the graph: give a starting node color 0, its neighbours color 1, their neighbours color 0, …
- If an edge ever connects two nodes of the same color, the graph is not bipartite. Remember to start a new BFS in every component.
Approach
color[v] = −1 means uncolored. For each uncolored node, color it 0 and BFS: every uncolored neighbour gets the opposite color; a neighbour that already has the same color proves an odd cycle — print NO. If all components finish, print YES. A graph is bipartite exactly when it has no odd cycle.
Complexity: O(n + m) time · O(n + m) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> col(n + 1, -1);
for (int s = 1; s <= n; s++) {
if (col[s] != -1) continue;
col[s] = 0;
queue<int> q;
q.push(s);
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]) {
cout << "NO\n";
return 0;
}
}
}
}
cout << "YES\n";
return 0;
}Python solution
import sys
from collections import deque
data = list(map(int, sys.stdin.read().split()))
n, m = data[0], data[1]
adj = [[] for _ in range(n + 1)]
for i in range(m):
u, v = data[2 + 2 * i], data[3 + 2 * i]
adj[u].append(v)
adj[v].append(u)
col, ok = [-1] * (n + 1), True
for s in range(1, n + 1):
if col[s] != -1 or not ok:
continue
col[s] = 0
q = deque([s])
while q and ok:
u = q.popleft()
for v in adj[u]:
if col[v] == -1:
col[v] = 1 - col[u]
q.append(v)
elif col[v] == col[u]:
ok = False
break
print("YES" if ok else "NO")Java solution
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int n = (int) in.nval;
in.nextToken();
int m = (int) in.nval;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
for (int i = 0; i < m; i++) {
in.nextToken();
int u = (int) in.nval;
in.nextToken();
int v = (int) in.nval;
adj.get(u).add(v);
adj.get(v).add(u);
}
int[] col = new int[n + 1];
Arrays.fill(col, -1);
for (int s = 1; s <= n; s++) {
if (col[s] != -1) continue;
col[s] = 0;
ArrayDeque<Integer> q = new ArrayDeque<>();
q.add(s);
while (!q.isEmpty()) {
int u = q.poll();
for (int v : adj.get(u)) {
if (col[v] == -1) { col[v] = 1 - col[u]; q.add(v); }
else if (col[v] == col[u]) {
System.out.println("NO");
return;
}
}
}
}
System.out.println("YES");
}
}