Bipartite Graph Check

Write a program to check Bipartite Graph

Example 1:

Input : n=6, edges={{1,2},{1,3},{2,4},{3,5},{5,6}}
Output: Graph is Bipartite

 Example 2:

Input : n=6, edges={{1,2},{1,3},{2,4},{3,5},{5,6},{1,5}
Output: Graph is not Bipartite

Approach:

Java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class BipartiteGraphCheck {
    // Adjacency Lists
    static ArrayList<ArrayList<Integer>> adj =
             new ArrayList<>();

    public static void main(String[] args) {

        int n = 6;
        for (int i = 0; i <=n; i++)
            adj.add(new ArrayList<>());

        addEdge(adj, 1, 2);
        addEdge(adj, 1, 3);
        addEdge(adj, 2, 4);
        addEdge(adj, 3, 5);
        addEdge(adj, 5, 6);
        if (isBipartite(n))
            System.out.println("Graph is Bipartite");
        else
            System.out.println("Graph is not Bipartite");
    }

    // Method to check graph is bipartite
    private static boolean isBipartite(int n) {

        // vector to store the distance
        // of all nodes initialize with INT_MAX(infinite)
        int part[] = new int[n+1];
        for (int i = 0; i <part.length; i++) {
            part[i] = -1;
        }

        // variable hold the bipartiteness
        // of the graph
        boolean isBipartite = true;

        // queue to hold the incomimg
        // nodes
        Queue<Integer> q = new LinkedList<Integer>();
        // iterate for all nodes
        for (int i = 1; i <= n; i++) {

            // if node is not partitioned
            if (part[i] == -1) {

                // push into the queue
                q.add(i);

                // assine side as 0
                part[i] = 0;

                // iterate till the queue is not empty
                while (!q.isEmpty()) {
                    int curr = q.poll();

                    // iterate for adjacency list
                    // of the current node
                    for (int child : adj.get(curr)) {
                        // if not partioned then
                        // partitioned opposide side
                        // of the current element
                        if (part[child] == -1) {
                            part[child] = part[curr] ^ 1;
                            q.add(child);
                        }
                        // if already partitione then
                        // if both are are same side then bipartite
                        // will we false else bipartite as true
                        // so update this as bipartite&=part[child]!=part[curr]
                        else
                            isBipartite &= part[child] != part[curr];

                    }
                }
            }
        }
        return isBipartite;
    }

    private static void addEdge(ArrayList<ArrayList<Integer>> g,
             int u, int v) {
        // undirected graph
        g.get(u).add(v);
        g.get(v).add(u);
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// adjacency list
vector<int> arr[1000001];


//function to add the edges into
//the graph
void addEdge(int u,int v)
{

    //undirected graph
    arr[u].push_back(v);
    arr[v].push_back(u);
}
//function to check the graph
//is bipartite or not
bool isBipartite(int n)
{

  //to hold the which side the
  //node comes
   vector<int> part(n+1,-1);

  //variable hold the bipartiteness
  //of the graph
   bool is_bipartite=true;

 //queue to hold the incomimg
 //nodes
   queue<int> q;
 //iterate for all nodes
   for(int i=1;i<=n;i++)
     {

        //if node is not partitioned
    if(part[i]==-1)
          {

      //push into the queue
         q.push(i);

        //assine side as 0
         part[i]=0;

       //iterate till the queue is not empty
       while(!q.empty())
            {
               int curr=q.front();
                  q.pop();

           //iterate for adjacency list
            //of the current node
            for(int child:arr[curr])
                     {
                  //if not partioned then
                  //partitioned opposide side
                 //of the current element
                 if(part[child]==-1)
                     {
                        part[child]=part[curr]^1;
                        q.push(child);
                      }
                //if already partitione then 
                //if both are are same side then bipartite 
                //will we false else bipartite as true
                //so update this as bipartite&=part[child]!=part[curr]
                  else
                    is_bipartite&=part[child]!=part[curr];
                          
                }
            }
         }
    }
    return is_bipartite;
   
}
int main()
{
  
  int n=6;
  addEdge(1,2);
  addEdge(1,3);
  addEdge(2,4);
  addEdge(3,5);
  addEdge(5,6); 
  if(isBipartite(n))
     cout<<"Graph is Bipartite\n";
  else
    cout<<"Graph is not Bipartite\n";
  return 0;    
}