Skip to content
AI360Xpert
Back to Graphs
Medium

Redundant Connection

In this problem, a tree is an undirected graph that is connected and has no cycles. You are given a graph that started as a tree with `n` nodes labeled from `1` to `n`, with one additional edge added. The added edge has two different vertices chosen from `1` to `n`, and was not an edge that already existed. The graph is represented as an array `edges` of length `n` where `edges[i] = [ai, bi]` indicates that there is an edge between nodes `ai` and `bi` in the graph. Return an edge that can be removed so that the resulting graph is a tree of `n` nodes. If there are multiple answers, return the answer that occurs last in the input.

Examples

Input:edges = [[1,2],[1,3],[2,3]]
Output:[2,3]
The edges form a cycle [1,2,3]. Removing [2,3] breaks the cycle and leaves a tree. [2,3] is the last edge in the input that creates the cycle.
Input:edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output:[1,4]
The edges [1,2], [2,3], [3,4], [1,4] form a cycle. Removing [1,4] breaks it and results in a valid tree.

Constraints

  • n == edges.length
  • 3 <= n <= 1000
  • edges[i].length == 2
  • 1 <= ai < bi <= edges.length
  • ai != bi
  • There are no repeated edges.
  • The given graph is connected.

Union Find (Disjoint Set)

Approach

We can use the Union-Find algorithm to detect cycles efficiently. We iterate through each edge. For each edge `(u, v)`, we check if `u` and `v` belong to the same set (i.e., they have the same parent/root). If they have the same root, adding this edge would create a cycle, so this is the redundant edge we should remove. If they do not have the same root, we union their sets and continue.

Complexity Analysis

Time Complexity
O(n * α(n))
Space Complexity
O(n)

The time complexity is effectively O(n) because the inverse Ackermann function α(n) grows extremely slowly and is ≤ 4 for all practical values of n. Space complexity is O(n) for the parent and rank arrays.

Solution.java
class Solution {    public int[] findRedundantConnection(int[][] edges) {        int n = edges.length;        int[] parent = new int[n + 1];        int[] rank = new int[n + 1];                // Initialize parents and ranks        for (int i = 1; i <= n; i++) {            parent[i] = i;            rank[i] = 1;        }                // Process each edge        for (int[] edge : edges) {            if (!union(parent, rank, edge[0], edge[1])) {                return edge; // Cycle detected            }        }                return new int[0];    }        // Find the root of a node with path compression    private int find(int[] parent, int n) {        if (parent[n] != n) {            parent[n] = find(parent, parent[n]);        }        return parent[n];    }        // Union two components by rank. Returns false if they are already connected.    private boolean union(int[] parent, int[] rank, int n1, int n2) {        int p1 = find(parent, n1);        int p2 = find(parent, n2);                if (p1 == p2) {            return false; // Already in the same set        }                // Union by rank        if (rank[p1] > rank[p2]) {            parent[p2] = p1;            rank[p1] += rank[p2];        } else {            parent[p1] = p2;            rank[p2] += rank[p1];        }                return true;    }}