Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Try to 2-color the graph: give a starting node color 0, its neighbours color 1, their neighbours color 0, …
  2. 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");
    }
}

Solve Is Graph Bipartite online · All practice problems