⬆️ Beats 100% | C++ | Python |  Simplified | Union-Find | Seperate Modular Class
IntuitionThe problem requires identifying an extra edge in a graph that, when added, results in a cycle. This "redundant connection" is the first edge in the gi
# Intuition

The problem requires identifying an extra edge in a graph that, when added, results in a cycle. This "redundant connection" is the first edge in the given list that **causes the graph to become cyclic**. Since the initial graph has no cycles, our goal is to **detect the earliest edge that completes a cycle**.

We are going to utilize a Disjoint Set (Union-Find) data structure. By maintaining disjoint sets of connected nodes, we can efficiently determine whether adding an edge would form a cycle. **If two nodes in an edge already belong to the same set, then adding that edge would create a cycle, making it redundant.**

# Approach
1. **Disjoint Set Representation:**
We initialize a Disjoint Set (also known as Union-Find) where each node is its own parent. This structure helps in keeping track of connected components in the graph.

2. **Union-Find with Path Compression:**
Find operation: This method retrieves the root representative of a node, utilizing path compression to optimize future queries.
Union operation: This method merges two sets, connecting two previously unlinked components. If the nodes are already in the same set, it means adding the edge creates a cycle.

3. **Processing Edges:**
Iterate through each edge in the input. Use the Union operation to merge sets. If merging fails (i.e., both nodes are already connected), return the current edge as it is the first one forming a cycle.

4. **Termination:**
Once a redundant edge is found, return it immediately. If no cycle is detected (which is guaranteed not to happen per the problem constraints), return an empty result.

# Complexity Analysis

- **Time Complexity:**

Each find operation has nearly constant time complexity due to path compression **(O(α(N))**, where α is the inverse Ackermann function).

We perform find and union for each edge, leading to an overall time complexity of **O(E α(V))**, which is almost linear in practice.

- **Space Complexity:**

No extra space apart from a few integer variables is used, making the total space complexity O(V).

# Code
```cpp []
// Simplified DS implementation for easy understanding, can be optimized further by using Union by Size/ Rank
class DisjointSet {
private:
    vector<int> parent;
public:
    DisjointSet(int n) {
        parent.resize(n+1);
        for (int i = 0; i < n + 1; ++i) {
            parent[i] = i; //initially all nodes are set as independent 
        }
    }
    int find(int u) {
        if (parent[u] == u) return u;
        return parent[u] = find(parent[u]);
    }
    bool Union(int u, int v) {
        int parU = find(u);
        int parV = find(v);
        if (parU != parV) { // not part of the set yet
            parent[parV] = parU;
            return true;
        } else return false; // already part of the set

    }
};
class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size(); //here graphs with n nodes have n edges 
        DisjointSet ds(n);
        for (const auto &edge : edges) {
            int u = edge[0], v = edge[1];
            if (!ds.Union(u, v)) return edge;
        }
        return {};
    }
};
```
```python []
class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n + 1))  # Initialize each node as its own parent

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

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u != root_v:
            self.parent[root_v] = root_u  # Merge sets
            return True
        return False  # redundant edge detected

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)  # Number of nodes (since n edges for n nodes)
        ds = DisjointSet(n)
        for u, v in edges:
            if not ds.union(u, v):
                return [u, v]  # Return the first redundant edge
        return []        
```
['Union Find', 'Graph', 'C++', 'Python3']