09-Redundant-Connection.md

Redundant Connection

Problem Link

https://leetcode.com/problems/redundant-connection/

---

Pattern

• Union-Find

---

Approach

Process edges one by one and return the first edge that connects two nodes already in the same component.

---

Time Complexity

O(e \u03b1(n))

Space Complexity

O(n)

---

Java Solution

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        int[] parent = new int[n + 1];
        for (int i = 1; i <= n; i++) parent[i] = i;
        for (int[] edge : edges) {
            int a = find(parent, edge[0]);
            int b = find(parent, edge[1]);
            if (a == b) return edge;
            parent[a] = b;
        }
        return new int[0];
    }

    private int find(int[] parent, int x) {
        if (parent[x] != x) parent[x] = find(parent, parent[x]);
        return parent[x];
    }
}