Discussion on: Solution: Is Graph Bipartite?

[Rohith V]

We can solve it using Union Find Template :

class Solution {
    public boolean isBipartite(int[][] graph) {
        int row = graph.length;
        UnionFind uf = new UnionFind(row);
        for (int i=0; i<row; i++) {
            for (int j=0; j<graph[i].length; j++) {
                if (uf.find(i) == uf.find(graph[i][j]))
                    return false;
                uf.union(graph[i][0], graph[i][j]);
            }
        }
        return true;
    }
}

class UnionFind {
    int size;
    int component;
    int [] parent;
    int [] rank;

    public UnionFind(int n) {
        size = n;
        component = n;
        parent = new int [n];
        rank = new int [n];
        for (int i=0; i<n; i++)
            parent[i] = i;
    }

    public int find(int p) {
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;
        if (rank[rootP] < rank[rootQ]) {
            parent[p] = rootQ;
        }
        else {
            parent[q] = rootP;
            if (rank[rootP] == rank[rootQ])
                rank[rootP] += 1;
        }
        component -= 1;
    }
}