C++ Program to Check if a Given Graph is Bipartite

Code:

#include     bits/stdc++.h

using namespace std;

int n,e,i,j;
vector > graph;
vector color;
bool vis[100011];

bool isBipartite()
{
    color[0] = 1; // Mark colour as 1 for first vertex.
    queue q;
    q.push(0);
    while (!q.empty())
    {
        int temp = q.front();
        q.pop();
        for (i=0;i
        {
            if (graph[temp][i] && color[i] == -1) //if there is an edge, and colour is not assigned
            {
                color[i] = 1 - color[temp];
                q.push(i);
            }
            else if (graph[temp][i] && color[i] == color[temp]) // if there is an edge and both vertices have same colours
                return 0;                                   // graph is not bipartite
        }
    }
    return 1;
}

int main()
{
    int x,y;
    cout<<"Enter number of vertices and edges respectively:";
    cin>>n>>e;
    cout<<"\n";
    graph.resize(n);
    color.resize(n,-1);
    memset(vis,0,sizeof(vis));
    for(i=0;i
        graph[i].resize(n);
    for(i=0;i
    {
        cout<<"\nEnter edge vertices of edge "<
        cin>>x>>y;
        x--; y--;
        graph[x][y]=1;
        graph[y][x]=1;
    }
    if(isBipartite())
        cout<<"Yes, The given graph is Bipartite.\n";
    else
        cout<<"No, The given graoh is not Bipartite.\n";
    return 0;
}


Output:

Case 1:
Enter number of vertices and edges respectively:6 5


Enter edge vertices of edge 1 :1 2

Enter edge vertices of edge 2 :1 3

Enter edge vertices of edge 3 :1 4

Enter edge vertices of edge 4 :1 5

Enter edge vertices of edge 5 :1 6
Yes, The given graph is Bipartite.


Case 2:
Enter number of vertices and edges respectively:5 5


Enter edge vertices of edge 1 :1 2

Enter edge vertices of edge 2 :1 3

Enter edge vertices of edge 3 :1 4

Enter edge vertices of edge 4 :1 5

Enter edge vertices of edge 5 :2 3
No, The given graoh is not Bipartite.


More C++ Programs: