Redundant Connection

The problem

You are given edges, the edges of an undirected graph with nodes numbered 1 to n. An edge [a,b] joins nodes a and b in both directions. The graph began as a tree: connected, meaning every node can reach every other, and with no cycle (a route that returns to its start without using an edge twice). A tree with n nodes has n - 1 edges. Then one extra edge was added, so there are n edges and exactly one cycle. Return an edge whose removal leaves a tree again. If several qualify, return the one that comes last in edges, written exactly as it appears there.

What to write

function solve(edges: number[][]): number[]

Input
edges = [[1,2],[1,3],[2,3]]

Output
[2,3]

Input
edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]

Output
[1,4]

Constraints

The graph is connected.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The graph has exactly one cycle, and the edges that qualify are exactly the edges on that cycle: removing any one of them leaves everything connected, while removing any other edge splits the graph in two. So the real question is: which edge of the cycle comes last in edges?

2. Hint 2: Ask a smaller question

   Draw the edges of example 2 one at a time, in the order they are given. At which edge does a closed loop first appear in your drawing? What was already true of that edge's two ends before you drew it?

3. Hint 3: Name the pattern

   An edge closes the cycle exactly when its two ends are already connected by earlier edges. Asking "already connected?" again and again while links are only ever added is the signal for union-find. Union-find keeps nodes in groups, with two operations: find tells which group a node is in, and union merges two groups. Read the lesson on union-find.

4. Hint 4: State the invariant

   Every node has a parent link, and climbing the links from any node ends at one node that is its own parent: the root of its group. After each edge is handled, two nodes have the same root exactly when the edges read so far connect them.

5. Hint 5: Sketch the pseudocode

   Every node, 1 to the number of edges, starts as its own parent with size 1. Find a root: while a node is not its own parent, point it at its grandparent and move there. For each edge, find both roots. Equal: return the edge. Otherwise put the smaller group's root under the larger and add the sizes.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Union the endpoints of each edge. An edge joining nodes already in one component closes the unique cycle.

The slow way

Add the edges one at a time. Before adding an edge, walk the graph built so far from one of its ends and see whether you can already reach the other end. If you can, that edge closes the cycle. It is correct, but each walk can visit every node, so n edges cost about n × n steps.

The insight

You never need the route between two nodes, only a yes or no: are they already in one connected group, also called a component? Union-find answers that without walking the graph. Each node stores one link, to its parent, and following parents from any node of a group ends at the group's root. Find is that climb. Union joins two groups by putting one root under the other.

Step by step

1. Start every node as the root of its own group of size 1. Before any edge is read, no two nodes are connected, so each node is a group by itself. A node that is its own parent is a root. The sizes are needed later, to decide which group goes under which.
2. Find a node's root: climb the parent links, halving the path as you go. Two nodes are in the same group exactly when their climbs end at the same root. Pointing each visited node at its grandparent makes the path about half as long, so later climbs from there are shorter.
3. Take the edges in order and find the roots of both ends. The roots say whether the edges read so far already connect the two ends. Reading in input order matters, because the answer is the cycle edge that comes last.
4. Same root: the ends are already connected, so this edge is the answer. A route between the two ends already exists, so this edge adds a second one and closes the cycle. All the other cycle edges were read before this one, which makes this edge the last of them.
5. Different roots: put the smaller group under the larger group's root. One root becomes the parent of the other, and two groups are now one. Putting the smaller under the larger keeps climbs short: a node's climb grows by one link only when its group at least doubles.

The same numbered steps are the comments in each solution.

function solve(edges) {
  // 1. Start every node as the root of its own group of size 1
  // A tree with n nodes has n - 1 edges, so the extra edge makes as many edges
  // as nodes. Nodes are numbered from 1, so slot 0 of each list stays unused.
  const parent = Array.from({ length: edges.length + 1 }, (_, i) => i),
    size = Array(edges.length + 1).fill(1);
  // 2. Find a node's root: climb the parent links, halving the path as you go
  function find(x) {
    // A root is its own parent, so the climb stops there.
    while (x !== parent[x]) {
      // Point the node at its grandparent, then move up to it.
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  }
  // 3. Take the edges in order and find the roots of both ends
  for (const [a, b] of edges) {
    let x = find(a),
      y = find(b);
    // 4. Same root: the ends are already connected, so this edge is the answer
    if (x === y) return [a, b];
    // 5. Different roots: put the smaller group under the larger group's root
    if (size[x] < size[y]) [x, y] = [y, x];
    parent[y] = x;
    size[x] += size[y];
  }
  // The input always holds one extra edge, so this line is never reached.
  return [];
}

function solve(edges: number[][]): number[] {
  // 1. Start every node as the root of its own group of size 1
  // A tree with n nodes has n - 1 edges, so the extra edge makes as many edges
  // as nodes. Nodes are numbered from 1, so slot 0 of each list stays unused.
  const parent = Array.from({ length: edges.length + 1 }, (_, i) => i),
    size = Array(edges.length + 1).fill(1);
  // 2. Find a node's root: climb the parent links, halving the path as you go
  function find(x: number): number {
    // A root is its own parent, so the climb stops there.
    while (x !== parent[x]) {
      // Point the node at its grandparent, then move up to it.
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  }
  // 3. Take the edges in order and find the roots of both ends
  for (const [a, b] of edges) {
    let x = find(a),
      y = find(b);
    // 4. Same root: the ends are already connected, so this edge is the answer
    if (x === y) return [a, b];
    // 5. Different roots: put the smaller group under the larger group's root
    if (size[x] < size[y]) [x, y] = [y, x];
    parent[y] = x;
    size[x] += size[y];
  }
  // The input always holds one extra edge, so this line is never reached.
  return [];
}

def solve(edges):
    # 1. Start every node as the root of its own group of size 1
    # A tree with n nodes has n - 1 edges, so the extra edge makes as many edges
    # as nodes. Nodes are numbered from 1, so slot 0 of each list stays unused.
    parent = list(range(len(edges) + 1))
    size = [1] * (len(edges) + 1)

    # 2. Find a node's root: climb the parent links, halving the path as you go
    def find(node):
        # A root is its own parent, so the climb stops there.
        while node != parent[node]:
            # Point the node at its grandparent, then move up to it.
            parent[node] = parent[parent[node]]
            node = parent[node]
        return node

    # 3. Take the edges in order and find the roots of both ends
    for a, b in edges:
        root_a, root_b = find(a), find(b)
        # 4. Same root: the ends are already connected, so this edge is the answer
        if root_a == root_b:
            return [a, b]
        # 5. Different roots: put the smaller group under the larger group's root
        if size[root_a] < size[root_b]:
            root_a, root_b = root_b, root_a
        parent[root_b] = root_a
        size[root_a] += size[root_b]
    # The input always holds one extra edge, so this line is never reached.
    return []

Example 2, traced

Input
edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]

Output
[1,4]

Why it works

After each edge that joins two groups, two nodes share a root exactly when the edges read so far connect them. So the first edge whose ends share a root is the one that closes the cycle. The graph has only one cycle, and the cycle's other edges all came earlier, so this is the last removable edge in the input.

Time and space

Time O(n α(n)), extra space O(n). Each of the n edges costs two finds and at most one merge. Halving paths and joining smaller under larger make a find almost constant: the α(n) in the bound grows so slowly it stays below 5 for any real input. The two lists hold n + 1 numbers each.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Join the two roots, not the two ends. With the second end as parent of the first, example 1 moves node 1 from under 2 to under 3, loses the link to 2, and returns an empty list.
• Nodes are numbered from 1, so each list needs one slot more than there are nodes. With one slot too few, Python stops with an index error at node 3 of example 1, and JavaScript quietly reads a missing value.
• The answer is not always the last edge of the input. In example 2 the last edge is [1,5], the only link to node 5. Removing that edge would cut node 5 off; the answer is [1,4].

Pattern

Union-find.

Keep going