Course4all
Join us on telegram
Home/dsa/Union Find/Redundant Connection

Redundant Connection

Master this topic with zero to advance depth.

Redundant Connection

In this problem, a tree (undirected graph with no cycles) was modified by adding one extra edge. Return the edge that can be removed so the resulting graph is a tree.

Medium

Examples

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
Approach 1

Level I: DFS (Incremental Cycles)

Intuition

For each new edge (u,v)(u, v), check if vv is already reachable from uu. If yes, this edge forms a cycle and is redundant.

⏱ O(V^2)💾 O(V)

Detailed Dry Run

Edge [1,2]: Added. Edge [1,3]: Added. Edge [2,3]: DFS(2) finds 3 via 1. Redundant!

java
class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        List<Integer>[] adj = new ArrayList[edges.length + 1];
        for (int i=0; i<=edges.length; i++) adj[i] = new ArrayList<>();
        for (int[] e : edges) {
            if (dfs(adj, e[0], e[1], new boolean[edges.length + 1])) return e;
            adj[e[0]].add(e[1]); adj[e[1]].add(e[0]);
        }
        return new int[0];
    }
    private boolean dfs(List<Integer>[] adj, int u, int target, boolean[] vis) {
        if (u == target) return true; vis[u] = true;
        for (int v : adj[u]) if (!vis[v] && dfs(adj, v, target, vis)) return true;
        return false;
    }
}
Approach 2

Level III: Union-Find (Efficiency)

Intuition

Use DSU to process edges. If an edge connects two nodes that already share the same root, that edge is the redundant one.

⏱ O(V \cdot \alpha(V))💾 O(V)

Detailed Dry Run

Edge [1,2]: Union(1,2). Edge [1,3]: Union(1,3). Edge [2,3]: find(2)=3, find(3)=3. Same component. Return [2,3].

java
class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int[] p = new int[edges.length + 1]; for(int i=0; i<p.length; i++) p[i]=i;
        for (int[] e : edges) {
            int r1 = find(p, e[0]), r2 = find(p, e[1]);
            if (r1 == r2) return e;
            p[r1] = r2;
        }
        return new int[0];
    }
    private int find(int[] p, int i) { return p[i]==i?i:(p[i]=find(p, p[i])); }
}
← Previous QuestionAccounts Merge
Next Question →Number of Connected Components