This One Trick with Union-Find Will Blow Your Mind! 🚀| beats 100% |
IntuitionThe problem requires us to find the redundant edge in a graph that forms a cycle. A cycle in a graph means there is an edge that connects two vertices
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem requires us to find the redundant edge in a graph that forms a cycle. A cycle in a graph means there is an edge that connects two vertices that are already connected through some other path. Using Union-Find (Disjoint Set Union - DSU), we can efficiently detect cycles by checking if two vertices of an edge are already in the same set. If they are, the edge is redundant.
# Approach
<!-- Describe your approach to solving the problem. -->
1. Initialize DSU:

    - Create a parent array to keep track of the root parent of each vertex.

    - Create a size array to implement union by size for optimization.

2. Process Each Edge:

    - For each edge, find the root parent of both vertices using the find function.

    - If the root parents are the same, the edge is redundant and forms a cycle.

    - If the root parents are different, perform a union operation to merge the two sets.

3. Return the Redundant Edge:

    - The last edge that forms a cycle is the redundant edge.
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$$O(Nα(N))$$

Here, 
N is the number of edges.

The find and union operations in DSU are nearly constant time due to path compression and union by size, where $α(N)$ is the inverse Ackermann function.
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$$O(N)$$
We use two arrays (parent and size) of size N+1 to store the DSU information.
# Code
```cpp []
class Solution {
    class DSU{
        vector<int> parent;
        vector<int> sz;
        public:
        DSU(int n){
            for(int i=0; i<=n; i++){
                parent.push_back(i);
                sz.push_back(1);
            }
        }
        int find(int u){
            if(parent[u] != u){
                parent[u] = find(parent[u]);
            }
            return parent[u];
        }
        void unionBySize(int u, int v){
            int pu = find(u);
            int pv = find(v);

            if(pu!=pv){
                if(sz[pu]>= sz[pv]){
                    parent[pv] = pu;
                    sz[pu]+=sz[pv];
                }
                else{
                    parent[pu] = pv;
                    sz[pv]+=sz[pu];
                }
            }
        }
    };
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        DSU dsu(n);
        vector<int> ans;
        for(int i=0; i<n; i++){
            int x = edges[i][0];
            int y = edges[i][1];

            int px = dsu.find(x);
            int py = dsu.find(y);

            if(px == py){
                ans = edges[i];
            }
            else{
                dsu.unionBySize(px,py);
            }
        }
        return ans;
    }
};
```
```java []
import java.util.*;

class Solution {
    class DSU {
        int[] parent;
        int[] size;

        public DSU(int n) {
            parent = new int[n + 1];
            size = new int[n + 1];
            for (int i = 0; i <= n; i++) {
                parent[i] = i; // Each node is its own parent initially
                size[i] = 1;   // Each set has size 1 initially
            }
        }

        // Find the root parent of a node with path compression
        public int find(int u) {
            if (parent[u] != u) {
                parent[u] = find(parent[u]); // Path compression
            }
            return parent[u];
        }

        // Union two sets by size
        public void unionBySize(int u, int v) {
            int pu = find(u);
            int pv = find(v);

            if (pu != pv) {
                if (size[pu] >= size[pv]) {
                    parent[pv] = pu;
                    size[pu] += size[pv];
                } else {
                    parent[pu] = pv;
                    size[pv] += size[pu];
                }
            }
        }
    }

    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        DSU dsu = new DSU(n);
        int[] result = new int[2];

        for (int[] edge : edges) {
            int x = edge[0];
            int y = edge[1];

            int px = dsu.find(x);
            int py = dsu.find(y);

            if (px == py) {
                // If both nodes are in the same set, this edge is redundant
                result[0] = x;
                result[1] = y;
            } else {
                // Otherwise, union the two sets
                dsu.unionBySize(x, y);
            }
        }

        return result;
    }
}
```
```python []
from typing import List

class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n + 1))  # Each node is its own parent initially
        self.size = [1] * (n + 1)  # Each set has size 1 initially

    def find(self, u: int) -> int:
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])  # Path compression
        return self.parent[u]

    def union_by_size(self, u: int, v: int) -> None:
        pu, pv = self.find(u), self.find(v)

        if pu != pv:
            if self.size[pu] >= self.size[pv]:
                self.parent[pv] = pu
                self.size[pu] += self.size[pv]
            else:
                self.parent[pu] = pv
                self.size[pv] += self.size[pu]

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        dsu = DSU(n)

        for x, y in edges:
            px, py = dsu.find(x), dsu.find(y)

            if px == py:
                return [x, y]  # This edge is redundant
            else:
                dsu.union_by_size(x, y)

        return []

```
Please upvote if you found this useful.


![Screenshot 2025-01-29 085335.png](https://assets.leetcode.com/users/images/07644fc1-63a6-4160-8da6-755eb318a6ad_1738121026.3004782.png)

['Union Find', 'Python', 'C++', 'Java']