DSU | Java | Explained with Comments
Every line of code is explained using comments (hope I didn\'t go overboard with comments \uD83D\uDE05)\n\nclass Solution {\n    \n    // "parents" and "ranks" 
Every line of code is explained using comments (hope I didn\'t go overboard with comments \uD83D\uDE05)\n```\nclass Solution {\n    \n    // "parents" and "ranks" arrays required for applying DSU\n    int[] parents;\n    int[] ranks;\n    \n    // v: vertex\n    private int find(int v) {\n        // using recursion, we\'ll find the "ultimate" leader after going from parent to parent (until v is its parent i.e. parents[v] == v), which will be the base case\n        if(parents[v] == v) {\n            return v;\n        }\n        \n        // we got our leader\n        int leader = find(parents[v]);\n        // for efficiency, now we\'ll update our parent with leader directly (so that next time we won\'t have to travel that long). This step is called "path compression"\n        parents[v] = leader;\n        \n        return leader;\n    }\n    \n    public int[] findRedundantConnection(int[][] edges) {\n        // tree: a connected, acyclic graph. Here, it is also "undirectional". \n        // no. of "edges" for this tree = no. of "vertices" - 1\n        \n        // vc: vertices count\n        int vc = edges.length;\n        \n        // We\'ll find the "redundant edge" using DSU (disjoint set union). For DSU, we actually need "edges" which are convenient given (instead of graph) \n        // looking at the input, we observe that the vertices are 1-indexed (will take care of that)\n        parents = new int[vc];\n        ranks = new int[vc];\n        \n        // initialization of parents and ranks\n        for(int i = 0; i < vc; i++) {\n            // initially, for each vertex parent is itself and rank is 0\n            parents[i] = i;\n            ranks[i] = 0;\n        }\n        \n        // preparation done for applying DSU: done using union() and find(). If we write a separate function union() for DSU (here done below), the above preparatory steps are done in there\n        \n        // now, we\'ll loop through each edge and check to see if it is redundant using DSU\n        for(int i = 0; i < edges.length; i++) {\n            // since vertices of the edges are given to be 1-indexed, we\'ll assume 1 as 0 (by subtracting u and v by 1 below)\n            int u = edges[i][0]; u--;\n            int v = edges[i][1]; v--;\n            \n            // lu: leader (group leader) of u, lv: leader (group leader) of v\n            int lu = find(u);\n            int lv = find(v);\n            \n            if(lu != lv) {\n                // u and v belong to different groups \n                // i.e. merging of those groups will take place (based on ranks of lu and lv)\n                // smaller rank vertex will go into the group of larger rank vertex\n                if(ranks[lu] < ranks[lv]) {\n                    // lu will make lv its parent\n                    parents[lu] = lv;\n                    \n                } else if(ranks[lu] > ranks[lv]) {\n                    // lv will make lu its parent\n                    parents[lv] = lu;\n                    \n                } else {\n                    // ranks[lu] == ranks[lv]\n                    // anyone can go in any group; but whoever\'s group it goes will increase its rank by 1\n                    parents[lu] = lv;\n                    ranks[lv]++; // increasing rank of lv by 1 (since lu merged its group under lv)\n                    \n                }\n                \n            } else {\n                // we found our redundant edge\n                return edges[i];\n            }\n        }\n        \n        // some invalid edge (will not hit this case)\n        return new int[] {-1, -1}; \n    }\n}\n```
['Union Find', 'Graph', 'Java']