Redundant Connection
Problem
You have a graph of n nodes labeled 1 to n, described by edges where edges[i] = [ai, bi] indicates an edge between nodes ai and bi. The graph started as a tree with n nodes and one additional edge was added, creating exactly one cycle. Return the edge that, if removed, would make the graph a tree again — if multiple answers exist, return the one that occurs LAST in the input.
Examples
Example 1
Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
Explanation: Removing [2,3] breaks the cycle 1-2-3-1; it's the last edge that creates the cycle.
Example 2
Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]
Explanation: The cycle is 1-2-3-4-1; [1,4] is the last edge processed that connects two already-connected nodes.
Constraints
- •
n == edges.length - •
3 <= n <= 1000 - •
edges[i].length == 2 - •
1 <= ai < bi <= edges.length - •
ai != bi - •
No repeated edges
Hints
Hint 1
Process edges in order, using Union-Find: for each edge, if the two nodes are ALREADY in the same component, this edge is the redundant one.
Hint 2
Union by rank/size and path compression keep find() close to O(1) amortized, so the whole scan is close to O(n).
Solutions
class UnionFind {
int[] parent, rank;
UnionFind(int n) {
parent = new int[n + 1];
rank = new int[n + 1];
for (int i = 0; i <= n; i++) parent[i] = i;
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]); // path compression
return parent[x];
}
boolean union(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return false; // already connected -> this edge is redundant
if (rank[rx] < rank[ry]) { int t = rx; rx = ry; ry = t; }
parent[ry] = rx;
if (rank[rx] == rank[ry]) rank[rx]++;
return true;
}
}
public int[] findRedundantConnection(int[][] edges) {
UnionFind uf = new UnionFind(edges.length);
for (int[] edge : edges) {
if (!uf.union(edge[0], edge[1])) return edge; // first edge that connects an already-joined pair
}
return new int[0];
}Time: O(n α(n)) — near-linear, α is the inverse Ackermann function · Space: O(n)