Problem Description

You are given a graph that was originally a tree with n nodes (labeled from 1 to n), but one extra edge has been added to it. This additional edge connects two different nodes that weren't already connected, creating exactly one cycle in the graph.

The graph is represented as an array edges where each element edges[i] = [ai, bi] indicates an undirected edge between nodes ai and bi.

Your task is to find and return one edge that can be removed to restore the graph back to a valid tree (a connected graph with no cycles). If there are multiple valid edges that could be removed, return the one that appears last in the input array.

For example, if you have nodes 1, 2, 3 forming a tree and then an edge is added between nodes 1 and 3 (creating a cycle), you need to identify which edge to remove to break the cycle and restore the tree structure.

The solution uses a Union-Find (Disjoint Set Union) data structure to detect the redundant edge. As we process each edge, we check if the two nodes it connects are already in the same connected component. If they are, adding this edge would create a cycle, so this is the redundant edge we need to return. If they aren't in the same component, we unite them. The first edge that would create a cycle when added is our answer.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem explicitly deals with an undirected graph that started as a tree with an additional edge added, creating a cycle.

Is it a tree?

• No: While the graph started as a tree, the addition of one extra edge means it's no longer a tree (it now contains exactly one cycle).

Is the problem related to directed acyclic graphs?

• No: The graph is undirected, and it actually contains a cycle (not acyclic).

Is the problem related to shortest paths?

• No: We're not finding shortest paths; we're identifying a redundant edge that creates a cycle.

Does the problem involve connectivity?

• Yes: The core of the problem is about connectivity - we need to identify when adding an edge would create a cycle (meaning the nodes are already connected through another path).

Disjoint Set Union

• Yes: This is the ideal approach. We can use DSU (Union-Find) to track connected components and detect when an edge would connect two nodes that are already in the same component.

Conclusion: The flowchart leads us to use Disjoint Set Union (DSU/Union-Find) to solve this problem. While DFS could also detect cycles, DSU is more efficient for this specific task of finding the redundant edge. As we process each edge, we check if it connects nodes already in the same component - if yes, that's our redundant edge.

Note: Although the problem can be solved with DFS by detecting cycles, the flowchart correctly guides us to DSU as it's a connectivity problem where we need to efficiently track and merge connected components.

Intuition

Think about what makes a tree special - it's a connected graph with exactly n-1 edges for n nodes, and there's exactly one path between any two nodes. When we add one extra edge to a tree, we create exactly one cycle because we're connecting two nodes that already have a path between them.

The key insight is that the redundant edge is the one that "completes" a cycle. As we build the graph edge by edge, everything is fine until we try to add an edge between two nodes that are already connected through some other path. That's the moment we create a cycle, and that edge is redundant.

To detect this, we can use the Union-Find (Disjoint Set Union) data structure. Initially, each node is in its own separate component. As we process each edge:

• If the two nodes are in different components, this edge is necessary to connect them, so we unite their components
• If the two nodes are already in the same component, adding this edge would create a cycle - this is our redundant edge!

Why does this work? Because in a tree, there should be exactly one way to reach any node from any other node. The moment we find an edge trying to connect two nodes that are already reachable from each other, we've found the edge that creates the alternative path (the cycle).

The beauty of this approach is that we process edges in order, so if multiple edges could be removed to eliminate the cycle, we naturally return the one that appears last in the input (the first one we encounter that would create a cycle).

Learn more about Depth-First Search, Breadth-First Search, Union Find and Graph patterns.

Solution Approach

The solution implements the Union-Find (Disjoint Set Union) data structure to detect the redundant edge. Here's how the implementation works:

1. Initialize the Parent Array

p = list(range(len(edges)))

We create a parent array p where initially each node is its own parent (representing separate components). The array is sized to len(edges) which works because we have n nodes and n edges.

2. Find Function with Path Compression

def find(x: int) -> int:
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]

This recursive function finds the root parent of a node. The key optimization here is path compression - when we find the root, we update p[x] to point directly to it, flattening the tree structure for faster future lookups.

3. Process Each Edge

for a, b in edges:
    pa, pb = find(a - 1), find(b - 1)

For each edge [a, b], we find the root parents of both nodes. Note that we use a - 1 and b - 1 because the nodes are labeled from 1 to n, but our array is 0-indexed.

4. Check for Cycle

if pa == pb:
    return [a, b]

If both nodes have the same root parent, they're already in the same connected component. Adding this edge would create a cycle, so this is our redundant edge - we return it immediately.

5. Union Operation

p[pa] = pb

If the nodes are in different components, we unite them by making one root the parent of the other. This merges the two components into one.

The algorithm processes edges in the order they appear in the input. The first edge that would create a cycle (connecting two already-connected nodes) is the answer. Since we process edges sequentially and return immediately upon finding the redundant edge, we naturally return the last valid answer if multiple edges could be removed.

Example Walkthrough

Let's walk through a concrete example to see how the Union-Find approach detects the redundant edge.

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

This represents a triangle where all three nodes are connected to each other. The redundant edge creates a cycle.

Initial State:

• Parent array p = [0, 1, 2] (each node is its own parent)
• Nodes 1, 2, 3 are in separate components

Step 1: Process edge [1,2]

• Find parents: find(0) = 0, find(1) = 1
• Different parents → No cycle yet
• Union: Set p[0] = 1
• Components: {1,2} and {3}

Step 2: Process edge [1,3]

• Find parents: find(0) = 1 (follows 0→1), find(2) = 2
• Different parents → No cycle yet
• Union: Set p[1] = 2
• Components: {1,2,3} all connected

Step 3: Process edge [2,3]

• Find parents: find(1) = 2 (follows 1→2), find(2) = 2
• Same parent (2) → Cycle detected!
• Return [2,3] as the redundant edge

The edge [2,3] is redundant because nodes 2 and 3 were already connected through node 1. Adding this edge creates a cycle: 1→2→3→1.

Another Example: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]

Processing edges in order:

1. [1,2]: Connect 1-2 (no cycle)
2. [2,3]: Connect 2-3 to existing component (no cycle)
3. [3,4]: Connect 3-4 to existing component (no cycle)
4. [1,4]: Nodes 1 and 4 already connected via 1→2→3→4 → Cycle!
5. Return [1,4] without processing [1,5]

The algorithm correctly identifies [1,4] as the edge that completes the cycle in the path 1→2→3→4→1.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × α(n)), where n is the number of edges and α(n) is the inverse Ackermann function. With path compression in the find function, each find operation takes nearly constant time O(α(n)), which is effectively O(1) for all practical values of n. Since we iterate through n edges and perform at most two find operations and one union operation per edge, the overall time complexity is O(n × α(n)), which can be approximated as O(n) for practical purposes.

However, the reference answer states O(n log n). This would be the case if we consider the worst-case scenario without path compression optimization, where the find operation could take O(log n) time in a balanced union-find tree. Since we perform up to 2n find operations (two for each edge), this gives us O(n log n).

The space complexity is O(n). The parent array p stores n elements (one for each node, where the number of nodes equals the number of edges in this problem since we're adding one edge to a tree). The recursion stack for the find function with path compression uses at most O(log n) space in the worst case, but this doesn't exceed the O(n) space used by the parent array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Parent Array Size

One of the most common mistakes is initializing the parent array with size n instead of n+1 when nodes are labeled from 1 to n.

Incorrect:

# If we have n nodes, this creates an array of size n
parent = list(range(n))  # [0, 1, 2, ..., n-1]

Problem: When accessing find(node - 1) where node could be n, we'd access index n-1 which works. However, if someone forgets to subtract 1 or makes the array too small, they'll get an IndexError.

Correct Approach:

# Option 1: Use len(edges) as size (since n edges means n nodes for this problem)
parent = list(range(len(edges)))

# Option 2: More explicit - create array of size n+1 to handle 1-indexed nodes
n = len(edges)  # n nodes, n edges (tree + 1 extra edge)
parent = list(range(n + 1))
# Then use find(node) directly without subtracting 1

2. Forgetting to Handle 1-Indexed Nodes

The problem states nodes are labeled from 1 to n, but arrays in Python are 0-indexed.

Incorrect:

for node1, node2 in edges:
    parent_1 = find(node1)  # Wrong! Treats nodes as 0-indexed
    parent_2 = find(node2)

Correct:

# Option 1: Subtract 1 when finding
for node1, node2 in edges:
    parent_1 = find(node1 - 1)
    parent_2 = find(node2 - 1)

# Option 2: Use 1-indexed parent array (size n+1)
parent = list(range(n + 1))  # Index 0 unused
for node1, node2 in edges:
    parent_1 = find(node1)  # Now works directly
    parent_2 = find(node2)

3. Missing Path Compression

Without path compression, the find operation becomes inefficient for deep trees.

Inefficient:

def find(x):
    while parent[x] != x:
        x = parent[x]
    return x

Optimized with Path Compression:

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # Compress path
    return parent[x]

4. Wrong Union Direction

While the direction of union doesn't affect correctness for this problem, inconsistent union can create unbalanced trees.

Less Optimal:

# Always making first parent point to second
parent[parent_1] = parent_2

Better Practice (Union by Rank/Size):

# Track rank or size for optimization
rank = [0] * (n + 1)
if rank[parent_1] < rank[parent_2]:
    parent[parent_1] = parent_2
elif rank[parent_1] > rank[parent_2]:
    parent[parent_2] = parent_1
else:
    parent[parent_2] = parent_1
    rank[parent_1] += 1

5. Not Returning the Edge Immediately

Some might try to collect all redundant edges and return the last one, which is unnecessary and inefficient.

Inefficient:

redundant_edges = []
for node1, node2 in edges:
    if find(node1 - 1) == find(node2 - 1):
        redundant_edges.append([node1, node2])
    else:
        union(node1 - 1, node2 - 1)
return redundant_edges[-1]  # Unnecessary storage

Efficient:

for node1, node2 in edges:
    if find(node1 - 1) == find(node2 - 1):
        return [node1, node2]  # Return immediately
    parent[find(node1 - 1)] = find(node2 - 1)

The immediate return works because we process edges in order, and the first edge that would create a cycle is the last one that could be removed (per problem requirements).