Bipartite graphs

A graph is bipartite if its vertices can be split into two groups so every edge crosses between groups.

Prerequisites: Basic C++ input/output, vectors, loops, and the preceding graph lessons.

Build the idea

1. Color a starting vertex 0.
2. Color each new neighbor with the opposite color.
3. An edge joining equal colors proves a conflict.
4. Repeat from uncolored vertices. A graph is bipartite exactly when it has no odd cycle.
5. c[v]=-1 means uncolored. Each new neighbor receives the opposite color; an already colored neighbor must disagree.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: c[v]=-1 means uncolored. Each new neighbor receives the opposite color; an already colored
// neighbor must disagree.
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
using namespace std;
bool bipartite(const vector<vector<int>>&g){
    vector<int>c(g.size(),-1);
    for(int s=1;s<(int)g.size();++s){
        if(c[s]==-1){
            queue<int>q;
            q.push(s);
            c[s]=0;
            while(!q.empty()){
                int v=q.front();
                q.pop();
                for(int u:g[v]){
                    if(c[u]==-1){
                        c[u]=c[v]^1;
                        q.push(u);
                    }
                    else if(c[u]==c[v]){
                        return false;
                    }
                }
            }
        }
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<vector<int>>graph(n+1);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    cout<<(bipartite(graph)?"YES":"NO")<<'\n';
}

Complexity analysis

O(V + E) time, O(V) space.

Example input and output

Read n m and m undirected edges (n≥1). Print YES if the entire graph is bipartite, otherwise NO. Disconnected components and self-loops are included in the check.

Input

3 3
1 2
2 3
3 1

Output

NO

The triangle is an odd cycle, so its last edge joins equal colors.

Practical applications

Use two-coloring for two-group constraints, odd-cycle detection, and bipartite matching prerequisites.

Check your understanding

Which cycle prevents bipartiteness?

Put it into practice

Split students into two teams so every listed rivalry crosses teams.