Is Graph Bipartite

Bipartite

If it is possible to divide vertices into two mutually exclusive and exhaustive sets such that all edges are across sets

mutually exclusive

• 2 sets can be created 
• intersection of 2 sets should be zero

Exhaustive

• all vertices should come

Above graph can't be bipartite.

Every non-cyclic graph is bipartite.

If cycle exists, it should be of even size only.

I/P: 

7

5

0 1 10

2 3 10

4 5 10

5 6 10

4 6 10

O/P: false

package pep.Day41;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Queue;

public class Is_Graph_Bipartite {
    static class Edge {
        int src;
        int nbr;

        Edge(int src, int nbr) {
            this.src = src;
            this.nbr = nbr;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int vtces = Integer.parseInt(br.readLine());
        ArrayList<Edge>[] graph = new ArrayList[vtces];
        for (int i = 0; i < vtces; i++) {
            graph[i] = new ArrayList<>();
        }

        int edges = Integer.parseInt(br.readLine());
        for (int i = 0; i < edges; i++) {
            String[] parts = br.readLine().split(" ");
            int v1 = Integer.parseInt(parts[0]);
            int v2 = Integer.parseInt(parts[1]);
            graph[v1].add(new Edge(v1, v2));
            graph[v2].add(new Edge(v2, v1));
        }
        HashMap<Integer, Integer> visited = new HashMap<>();
        boolean ans = true;
        for (int i = 0; i < vtces; i++) {
            if (!visited.containsKey(i))
                if (dfs(graph, i, visited) == false) {
                    ans = false;
                    break;
                }
        }

        System.out.println(ans);

    }

    private static boolean dfs(ArrayList<Edge>[] graph, int src, HashMap<Integer, Integer> visited) {
        Queue<Pair> queue = new ArrayDeque<>();
        int level = 0;

        queue.add(new Pair(src, level));
        boolean isBipartite = true;
        while (!queue.isEmpty()) {
            Pair out = queue.remove();

            if (!visited.containsKey(out.vertice)) {
                visited.put(out.vertice, out.level);
            } else {

                // conflict aa gya toh
                if (out.level != visited.get(out.vertice)) {
                    isBipartite = false;
                    return isBipartite;
                }
            }

            level++;
            for (Edge e : graph[out.vertice]) {
                if (!visited.containsKey(e.nbr)) {
                    queue.add(new Pair(e.nbr, level));
                }
            }

            if (visited.size() == graph.length)
                return isBipartite;
        }
        return true;
    }

    static class Pair {
        int vertice;
        int level;

        Pair(int vertice, int level) {
            this.vertice = vertice;
            this.level = level;
        }
    }
}