Redundant Connection

Q: What is the time complexity of Redundant Connection?

Union-find solves it in one pass over the n edges: O(n · α(n)) time, where α(n) is at most 4 in practice, and O(n) space. Peeling the leaves is O(n) as well. Trying each removal with a fresh search costs O(n²).

MediumUnion-find Graphs

+10

A network started as a tree: n nodes, numbered from 1 to n, joined by n-1 undirected edges with no cycle. Then one more edge was added between two nodes that were not directly joined, so the list edges now holds n edges and exactly one cycle.

Return an edge you can remove so that the other n-1 edges form a tree again. If several edges work, return the one that appears last in edges, as the pair [a, b] exactly as it is written there.

Function

findRedundantConnection(edges: integer-2d-array) → integer-array

edgesinteger-2d-array: the n undirected edges, each a pair [a, b] of nodes numbered from 1
Returnsinteger-array: the cycle edge that appears last in edges, written as it is there

Constraints

3 ≤ n ≤ 5000, where n = edges.length
edges[i] = [a, b] with 1 ≤ a, b ≤ n and a ≠ b
No edge appears twice, in either direction.
The edges connect all n nodes and hold exactly one cycle.

Examples

Input: edges = [[1, 2], [1, 3], [2, 3]]
Output: [2, 3]
Explanation: The three edges form the triangle 1, 2, 3, so removing any one of them leaves a tree. [2, 3] comes last in the list.

Input: edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
Output: [1, 4]
Explanation: The cycle is 1, 2, 3, 4, 1. The edge [1, 5] is not on it: removing it would cut node 5 off. Of the four cycle edges, [1, 4] appears last.

Follow-up

If the edges were directed and the original graph a rooted tree, which edge would you remove when the extra edge gives a node two parents?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Removing an edge leaves a tree exactly when the edge lies on the graph's one cycle, so the answer is the cycle edge that comes last in the list. Union-find finds it in one pass: add the edges in order, and the first edge whose ends are already connected is the answer.

Try removing each edge, last first

Correct, but does not finish on the largest tests

Intuition

Remove one edge and check whether the other n-1 edges form a tree. With n nodes and n-1 edges, they do exactly when one search from node 1 reaches all n nodes. Try the edges from the end of the list, so the first removal that passes is the latest one. Store each edge's index in the adjacency lists, and a search can step over the removed edge without rebuilding anything.

Each try is a full O(n) search, and there can be n tries: up to 2.5 × 10^7 steps when n = 5000.

Algorithm

Build adjacency lists that keep, for each neighbour, the index of the edge leading to it.
For skip from the last index down to 0, search from node 1 and ignore the edge with index skip.
Count the nodes the search reaches.
If it reaches all n, return edges[skip].

def findRedundantConnection(edges):
    n = len(edges)
    # graph[x] holds (neighbour, index of the edge) for every edge at node x.
    graph = [[] for _ in range(n + 1)]
    for i, (u, v) in enumerate(edges):
        graph[u].append((v, i))
        graph[v].append((u, i))
    # Try leaving out each edge, the last one first.
    for skip in range(n - 1, -1, -1):
        # Without edge skip, can node 1 still reach all n nodes?
        seen = [False] * (n + 1)
        seen[1] = True
        stack = [1]
        reached = 1
        while stack:
            node = stack.pop()
            for nxt, i in graph[node]:
                if i != skip and not seen[nxt]:
                    seen[nxt] = True
                    reached += 1
                    stack.append(nxt)
        # n-1 edges that connect n nodes form a tree.
        if reached == n:
            return edges[skip]
    return []

Peel off the leaves

Intuition

A leaf, a node with one edge, cannot be on a cycle, because a cycle enters and leaves each of its nodes. Removing a leaf can turn its neighbour into a leaf, so keep peeling until none is left. What remains is exactly the cycle, since each cycle node keeps its two cycle edges. In the second example node 5 is peeled, node 1 keeps two edges, and nodes 1 to 4 remain.

Any edge between two remaining nodes is a cycle edge, because a second link between cycle nodes would make a second cycle. So scan edges from the end and return the first edge whose ends both remain.

Algorithm

Build adjacency lists and count the degree of every node.
Push every node of degree 1 onto a stack.
Pop a leaf, set its degree to 0, and lower the degree of its remaining neighbour; push that neighbour when its degree drops to 1.
When the stack is empty, the nodes with a degree above 0 form the cycle.
Scan edges from the end and return the first edge whose ends both remain.

def findRedundantConnection(edges):
    n = len(edges)
    graph = [[] for _ in range(n + 1)]
    degree = [0] * (n + 1)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
        degree[u] += 1
        degree[v] += 1
    # A node with one edge cannot lie on the cycle. Remove it, and repeat.
    stack = [x for x in range(1, n + 1) if degree[x] == 1]
    while stack:
        leaf = stack.pop()
        degree[leaf] = 0
        for nxt in graph[leaf]:
            if degree[nxt] > 0:
                degree[nxt] -= 1
                if degree[nxt] == 1:
                    stack.append(nxt)
    # Only the cycle is left. Its edge that comes last in the list is the answer.
    for u, v in reversed(edges):
        if degree[u] > 0 and degree[v] > 0:
            return [u, v]
    return []

Union-find: the first edge that closes a loop

Intuition

Add the edges in list order and track which nodes are connected. Until the cycle closes, every edge joins two pieces with no path between them. The first edge whose ends are already connected closes the cycle. The cycle's other edges were added before it, so it is the cycle edge that appears last. In the second example [1, 4] finds nodes 1 and 4 already joined, and [1, 5] is never read.

The union-find keeps one array, parent; following the pointers from a node ends at the root of its piece. Attaching the smaller piece under the larger, and pointing nodes at their grandparents during find, keeps the chains short. Each operation then costs amortized O(α(n)), where α, the inverse Ackermann function, is at most 4 for any real input.

Algorithm

Point every node from 1 to n at itself, parent[x] = x, and give it size 1.
Go through edges in order. For [u, v], look up the root of u and the root of v.
If the roots match, [u, v] closes the cycle: return it as written.
If not, the larger piece absorbs the smaller: its root becomes the parent of the smaller root, and the sizes add up.

def findRedundantConnection(edges):
    n = len(edges)
    parent = list(range(n + 1))  # every node starts as its own group
    size = [1] * (n + 1)

    def find(x):
        # Walk up to the root, halving the path on the way.
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for u, v in edges:
        a, b = find(u), find(v)
        # u and v are already connected: this edge closes the cycle.
        if a == b:
            return [u, v]
        # Hang the smaller group under the larger one.
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]
    return []

Pitfalls and edge cases

Returning the last edge of the list. In the second example that is [1, 5], and removing it cuts node 5 off.
Scanning from the front after peeling. That returns the earliest cycle edge, [1, 2] in the second example.
Sorting or flipping the pair. If the list holds [3, 1], return [3, 1], not [1, 3].
Sizing arrays for nodes 0 to n-1. Nodes are numbered from 1, so node n needs an array of n+1 slots.
Recursing around the cycle. It can pass through all 5000 nodes, five times Python's default recursion limit, so use an explicit stack and a loop in find.

Frequently asked questions3

What is the time complexity of Redundant Connection?

Union-find solves it in one pass over the n edges: O(n · α(n)) time, where α(n) is at most 4 in practice, and O(n) space. Peeling the leaves is O(n) as well. Trying each removal with a fresh search costs O(n²).

Which edges can be removed to leave a tree?

Exactly the edges on the cycle. Each of them has a second route between its ends around the rest of the cycle, so removing it keeps the graph connected. Any other edge is the only link between two parts of the graph, and removing it splits them.

Can Redundant Connection be solved with DFS?

Yes. Before adding each edge, search from one end over the edges added so far; the first edge whose other end is already reachable is the answer. That costs O(n) per edge, O(n²) in total, where union-find answers the same question in near constant time.

def findRedundantConnection(edges):
    # Write code here

Test #1

Test #2

Argument

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

Expected Output

[2, 3]

Redundant Connection

Function

Constraints

Examples

Hints

Solution

Try removing each edge, last first

Peel off the leaves

Union-find: the first edge that closes a loop

Pitfalls and edge cases

Frequently asked questions3

Similar problems