Bipartite Graph

shriyanshi24jindal

Mar 29th, 2026

117

Never

Not a member of GistPad yet? Sign Up, it unlocks many cool features!

Java 10.77 KB | None | 0 0

copy raw download clone embed print report

class Solution {
public boolean isBipartite(int V, int[][] edges) {
// create a adjacency list
ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
for(int i=0; i<V; i++)
{
adj.add(new ArrayList<Integer>());
}
// fill the adjacency list
for(int[] edge : edges)
{
int u = edge[0];
int v = edge[1];
// undirected graph
adj.get(u).add(v);
adj.get(v).add(u);
}
int[] color = new int[V];
Arrays.fill(color, -1);
for(int i=0; i<V; i++)
{
// only start BFS if node is uncolored
if (color[i] == -1)
{
if(bfs(adj, color, i) == false)
return false;
}
}
return true;
}
public boolean bfs(ArrayList<ArrayList<Integer>> adj, int[] color, int node)
{
Queue<Integer> q = new LinkedList<>();
q.add(node);
color[node] = 0;
while(!q.isEmpty())
{
int u = q.poll();
for(int v : adj.get(u))
{
// neighbour node and current node has same color, so not a bipartite graph
if(color[v] == color[u])
return false;
// assign opposite color
else if(color[v] == -1)
{
// assigning opposite color
color[v] = 1 - color[u];
q.add(v);
}
}
}
return true;
}
}

RAW Paste Data Copied

class Solution {
    public boolean isBipartite(int V, int[][] edges) {

// create a adjacency list
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        for(int i=0; i<V; i++)
        {
            adj.add(new ArrayList<Integer>());
        }
        
        // fill the adjacency list
        for(int[] edge : edges)
        {
            int u = edge[0];
            int v = edge[1];
            
            // undirected graph
            adj.get(u).add(v);
            adj.get(v).add(u);
        }
        
        int[] color = new int[V];
        Arrays.fill(color, -1);
        
        for(int i=0; i<V; i++)
        {
            // only start BFS if node is uncolored
            if (color[i] == -1) 
            {  
                if(bfs(adj, color, i) == false)
                    return false;
            }
        }
        return true;
    }
    
    public boolean bfs(ArrayList<ArrayList<Integer>> adj, int[] color, int node)
    {
        Queue<Integer> q = new LinkedList<>();
        q.add(node);
        color[node] = 0;
        
        while(!q.isEmpty())
        {
            int u = q.poll();
            
            for(int v : adj.get(u))
            {
                // neighbour node and current node has same color, so not a bipartite graph
                if(color[v] == color[u])
                    return false;
                    
                // assign opposite color
                else if(color[v] == -1)
                {
                    // assigning opposite color
                    color[v] = 1 - color[u];
                    q.add(v);
                }
            }
        }
        return true;
    }
}