Redundant Connection
MediumThe problem
edges describes a connected graph of nodes 1 to n that started as a tree (no cycles) and then got one extra edge added. Each edge is a pair [a, b]. Return an edge that can be removed so that the graph is a tree again. If several edges work, return the one that appears last in edges.
- Example 1Input: edges = [[1, 2], [1, 3], [2, 3]]Output: [2, 3]
1, 2 and 3 form a triangle. Removing the last edge breaks it.
- Example 2Input: edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]Output: [1, 4]
Nodes 1, 2, 3, 4 form a loop. Among the loop edges, [1, 4] is the last one listed.
- 3 ≤ n = len(edges) ≤ 1,000
- Nodes are numbered from 1 to n
- There are no repeated edges
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
A tree has no cycles. Which edge is the first one that connects two nodes that are already connected?
The idea
Union-find: for each edge, if both endpoints already share a root that edge closes the cycle; otherwise union them.
Target: O(n α(n)) time
Go function shape
func findRedundantConnection(edges [][]int) []intReference solution
Tested with go test. Try it yourself first, then compare.
// FindRedundantConnection: the edge that closes a cycle in a graph that was a tree plus one extra edge.
// The input has n nodes and n edges, so nodes 1..n fit in n+1 slots. If both ends are already connected, this edge makes the cycle.
func FindRedundantConnection(edges [][]int) []int {
u := NewUF(len(edges) + 1) // nodes are labelled 1..n
for _, e := range edges {
if !u.Union(e[0], e[1]) {
return e
}
}
return nil
}