Problem overview
A tree is a connected undirected graph with no cycle. You get a tree of n nodes, numbered 1 to n, plus one extra edge between two nodes that were not joined before. The method findRedundantConnection receives the int[][] named edges, which has n edges, and returns an edge whose removal leaves a tree of all n nodes. When several edges would work, it returns the one that comes last in edges.
For [[1,2],[1,3],[2,3]] the three edges form the cycle 1 - 2 - 3 - 1. Removing any of them leaves a tree, and [2, 3] comes last, so that is the answer. For [[1,2],[2,3],[3,4],[1,4],[1,5]] the cycle is 1 - 2 - 3 - 4 - 1, and the answer is [1, 4]. The last edge of the input, [1, 5], is not on the cycle: removing it would cut node 5 off.
Approach: add edges one by one and watch for a cycle
The brute force tries each edge from the last backwards, removes it and runs a depth-first search to see whether the rest is still connected. That costs O(n²).
A faster way is to add the edges in the order given and keep track of which nodes are already connected. An edge whose two ends are already in the same group closes a cycle. The graph has exactly one cycle, and removing any edge of the cycle leaves a tree, while removing an edge that is not on it splits the tree. The cycle closes when its last edge arrives, because all its other edges came earlier. So the first edge that joins two already-connected nodes is the cycle's last edge in input order, and that is the answer, even if more edges follow it.
The data structure for "are these two nodes already connected?" is union-find (also called disjoint sets). Each group is stored as a tree: every node points to a parent, and the root, a node that is its own parent, names the group. Two nodes are in the same group exactly when they lead to the same root. Two improvements keep the trees shallow:
- Union by size. When two groups merge, the smaller tree goes under the larger one's root, so a node gets deeper only when its group at least doubles.
- Path halving. While walking up to a root, each node is pointed at its grandparent, so later walks are shorter.
With both, each operation costs O(α(n)) amortized, where α is the inverse Ackermann function, below 5 for any size a computer can hold.
On [[1,2],[3,4],[2,3],[4,5],[1,5]] the edges [1, 2] and [3, 4] make the groups {1, 2} and {3, 4}. Edge [2, 3] finds the two different roots 1 and 3 and merges them, and [4, 5] adds node 5. At [1, 5] both ends have root 1, so that edge closes the cycle, and the method returns [1, 5]. After the four merges the parent array is [0, 1, 1, 1, 1, 1]: every node points straight to node 1.
Step by step
- Store the edge count in
n. A tree ofnnodes hasn - 1edges, and the extra edge makesn, so the count is also the number of nodes. - Create
parentwithn + 1entries. Nodes start at 1, so nodeisits at indexiand index 0 is never used. - Create
sizethe same way.size[r]counts the nodes in the group whose root isr; only roots' entries are kept up to date. - Loop over the indexes and give every node its own group:
parent[i] = iandsize[i] = 1. A newintarray holds zeros, so the sizes must be set. - Loop over the edges in the given order, since the order decides which cycle edge is returned.
- Find both roots with the helper
find, intorootAandrootB. - If the roots are equal, return the edge. The ends were already connected, so this edge closes the cycle.
- Make
rootAthe larger group's root. Ifsize[rootA] < size[rootB], swap them through a temporary variable. - Merge by setting
parent[rootB] = rootAand addingsize[rootB]tosize[rootA]. - Return
new int[0]after the loop. The input always has an extra edge, so the method returns inside the loop and this line is never reached; Java requires a return on every path. - Write
find: whileparent[x] != x, setparent[x] = parent[parent[x]](path halving) and thenx = parent[x]. When the loop stops,xis the root, and the method returns it.
The solution in Java
class Solution {
public int[] findRedundantConnection(int[][] edges) {
int n = edges.length;
int[] parent = new int[n + 1];
int[] size = new int[n + 1];
for (int i = 0; i <= n; i++) {
parent[i] = i;
size[i] = 1;
}
for (int[] edge : edges) {
int rootA = find(parent, edge[0]);
int rootB = find(parent, edge[1]);
if (rootA == rootB) {
return edge;
}
if (size[rootA] < size[rootB]) {
int temp = rootA;
rootA = rootB;
rootB = temp;
}
parent[rootB] = rootA;
size[rootA] += size[rootB];
}
return new int[0];
}
int find(int[] parent, int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
}Java details: arrays are passed by reference, so when find changes parent, the caller sees it. That is intended, because path halving updates the shared structure. Assigning to the parameter x changes only the local copy of the number. The method returns edge, the very int[] from the input, not a copy. find uses a loop instead of recursion, so a long chain cannot overflow the call stack. For a chain 5 - 4 - 3 - 2 - 1 - 0 stored in parent as [0, 0, 1, 2, 3, 4], one call find(parent, 5) returns 0 and leaves parent as [0, 0, 1, 1, 3, 3]: the visited nodes now skip a level.
Complexity
Each of the n edges costs two find calls and at most one merge, each O(α(n)) amortized, so the time is O(n · α(n)), which is nearly O(n). The two arrays take O(n) extra space.
Edge cases and common mistakes
- Returning the last edge of the input. That is correct only if it is on the cycle. On the second example the input's last edge is
[1, 5], but the answer is[1, 4]. - Arrays of size
n. Nodenwould be out of range. Usen + 1. - Forgetting to start every node as its own root. With zeros in
parent, every node would appear to share root 0. - Merging nodes instead of roots. Set the parent of a root, not of the edge's endpoint, or the groups are not merged properly.
- A long chain. A path of 1000 nodes plus the edge
[1, 1000]returns[1, 1000].
Testing
These inputs were run against the solution above:
| edges | Result |
|---|---|
[[1,2],[1,3],[2,3]] | [2, 3] |
[[1,2],[2,3],[3,4],[1,4],[1,5]] | [1, 4] |
[[1,2],[3,4],[2,3],[4,5],[1,5]] | [1, 5] |
