Leet Code 684. Redundant Connection

isme pehle (1,2), then (2,3) aaya

jab (1,3) aaega tab humein cycle bnege, hence, woh redundant hai

hum aab koi bhi node hata skte hain, redundancy remove krne ke lea.

But cycle to bne hi last wale edge se the i.e. (1,3)

humein woh last node return krne hai jiski wjh se cycle bne hai

package pep.Day45;

public class LeetCode_684_Redundant_Connections {
    public int[] findRedundantConnection(int[][] graph) {
        // n kese niklega?
        // no. of edges =  no. of vertices +1
        int n = graph.length;

        // 1 -> n hai to n+1 ka size hona cheye
        parent = new int[n + 1];
        size = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            parent[i] = 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 {
                return edge;
            }
        }

        return new int[0];
    }

    int[] parent, size;

    public int findParent(int u) {

        return parent[u] == u ? u : (parent[u] = findParent(parent[u]));
    }

    public void merge(int u, int v) {

        if (size[u] >= size[v]) {
            parent[v] = u;
            size[u] += size[v];
        } else {
            parent[u] = v;
            size[v] += size[u];
        }
    }
}