C# Solution for Redundant Connection Problem
IntuitionThe problem requires us to find the redundant edge in a given tree with an extra edge, which means the graph initially had no cycles, but adding one ed
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem requires us to find the redundant edge in a given tree with an extra edge, which means the graph initially had no cycles, but adding one edge created exactly one cycle.

To efficiently detect this extra edge, we use the Union-Find (Disjoint Set) data structure. The key idea is:
1.	A tree is an acyclic connected graph with (n - 1) edges.
2.	Adding an extra edge creates exactly one cycle.
3.	Union-Find helps efficiently track connected components and detect cycles.

By processing edges one by one:
•	If two nodes of an edge already belong to the same connected component, adding the edge creates a cycle → this is the redundant edge.
•	Otherwise, we merge the sets (connect the nodes) using Union-Find with path compression and union by rank.

# Approach
<!-- Describe your approach to solving the problem. -->
Step 1: Initialize Union-Find Data Structures
	•	Create a parent[] array where each node is its own parent initially (parent[i] = i).
	•	Create a rank[] array initialized to 1 for all nodes to keep track of tree height.

Step 2: Process Each Edge in edges[]
	•	For each edge (u, v):
	•	Use Find to get the roots of u and v.
	•	If Find(u) == Find(v), it means u and v are already connected → Cycle detected → return [u, v].
	•	Otherwise, perform Union by Rank to merge the sets efficiently.

Step 3: Find with Path Compression
	•	When searching for the root of a node, we recursively update its parent to point directly to the root, flattening the tree.
	•	This optimizes future queries, making them nearly constant time O(α(n)).

Step 4: Union by Rank
	•	Attach the smaller tree under the larger tree to keep the height minimal.
	•	If both trees have the same rank, arbitrarily choose one as the root and increase its rank.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
•	Find operation with path compression runs in O(α(n)), where α(n) is the inverse Ackermann function (grows extremely slow, practically constant).
•	Union operation with rank also runs in O(α(n)).
•	Since we perform n union operations, the overall complexity is **O(n * α(n))`, which simplifies to O(n) for practical purposes.

Worst-Case Time Complexity: O(n)

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
•	Parent array (parent[]) → O(n)
•	Rank array (rank[]) → O(n)
•	No extra recursive calls or data structures beyond these.

Worst-Case Space Complexity: O(n)

# Code
```csharp []
public class Solution {
    public int[] FindRedundantConnection(int[][] edges) {
        int n = edges.Length;
        int[] parent = new int[n + 1];
        int[] rank = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }

        foreach (var edge in edges) {
            int u = edge[0], v = edge[1];
            if (!Union(u, v, parent, rank)) {
                return edge;
            }
        }
        return new int[0];
    }
    private int Find(int node, int[] parent) {
        if (parent[node] != node) {
            parent[node] = Find(parent[node], parent); 
        }
        return parent[node];
    }
    private bool Union(int u, int v, int[] parent, int[] rank) {
        int rootU = Find(u, parent);
        int rootV = Find(v, parent);

        if (rootU == rootV) return false; 

        if (rank[rootU] > rank[rootV]) {
            parent[rootV] = rootU;
        } else if (rank[rootU] < rank[rootV]) {
            parent[rootU] = rootV;
        } else {
            parent[rootV] = rootU;
            rank[rootU]++;
        }
        return true;
    }
}
```
['C#']