Graph - Disjoint Set Union

 

package pep.Day45;

public class DSU_Introduction {
    static int[] parent, size;

    public static int findParent(int u) {
        // agr jis node ke lea hum check kr rhe hain, woh khud apna leader/parent hai
        // to return kr denge node
        // nhi to recursive code chalaenge
        //return parent[u] == u ? u : findParent(parent[u]);

        // But return krte hue hume path compression bhi krna tha,
        // hence, recorsion se jo parent aaega uko update kr denge
        return parent[u] == u ? u : (parent[u] = findParent(parent[u]));
    }

    public static void merge(int u, int v) {
        // jiska bhi size bada hoga, woh parent banega dusre ka
        // also, size bhi bhadega
        if (size[u] >= size[v]) {
            parent[v] = u;
            size[u] = size[u] + size[v];
        } else {
            parent[u] = v;
            size[v] = size[v] + size[u];
        }
    }

    public static void unionFind(int n, int[][] graph) {
        parent = new int[n];
        size = new int[n];

        // har koi apna parent khud hai
        for (int i = 0; i < n; i++)
            parent[i] = i;

        // sabka size intitially 1 hai
        for (int i = 0; i < n; i++)
            size[i] = 1;

        for (int[] edge : graph) {
            int u = edge[0];
            int v = edge[1];

            int p1 = findParent(u);
            int p2 = findParent(v);

            if (p1 != p2) {
                merge(p1, p2);
            } else {
                System.out.println("Cycle");
            }
        }
    }


    static class Edge {
        int src;
        int nbr;

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

    }
}