In this problem, a tree is an undirected graph that is connected and has no cycles.

You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.

Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.

Thinking Process

In this problem, a tree is an undirected graph that is connected and has no cycles.

You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.

  • Model entities as nodes and relationships as edges.
  • Pick traversal (BFS/DFS) or shortest-path (Dijkstra) based on weights.
  • Union-Find helps when connectivity updates are frequent.
Graph BFS layers S a b t BFS: expand by layers (queue)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Recursive DFS (this problem) O(n) O(h) stack Natural for trees and graphs
Iterative DFS (stack) O(n) O(n) Avoid recursion depth limits
DFS with memoization O(n) O(n) Overlapping subproblems on graphs
Backtracking DFS O(2^n) typical O(n) Enumerate choices with pruning

Examples

Example 1:

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
Explanation: The edge [2,3] creates a cycle, so it should be removed.

Example 2:

Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]
Explanation: The edge [1,4] creates a cycle, so it should be removed.

Constraints

  • n == edges.length
  • 3 <= n <= 1000
  • edges[i].length == 2
  • 1 <= ai < bi <= edges.length
  • ai != bi
  • There are no repeated edges.
  • The given graph is connected.

DSU Template

Here’s the general template for Union-Find (DSU) with union by rank:

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        elif self.rank[x] > self.rank[y]:
            self.parent[y] = x
        else:
            self.parent[y] = x
            self.rank[x] += 1

        return True


class Solution:
    def findRedundantConnection(self, edges):
        n = len(edges)
        dsu = DSU(n + 1)

        for u, v in edges:
            if not dsu.unite(u - 1, v - 1):
                return [u, v]

        return []

Key Template Components:

  1. Data Structures:
    • parent[i]: Parent of node i (root if parent[i] == i)
    • rank[i]: Approximate depth of tree rooted at i
  2. Path Compression:
    • Flattens tree during find operation
    • Makes future finds faster
  3. Union by Rank:
    • Keeps trees balanced
    • Attaches smaller tree to larger tree
    • Only increases rank when ranks are equal
  4. Time Complexity:
    • Nearly O(1) per operation (inverse Ackermann function)
    • O(α(n)) where α grows extremely slowly

Complexity

Solution 1: DSU

Time Complexity: O(n × α(n)) ≈ O(n)

  • DSU operations: O(α(n)) per operation (nearly constant)
  • Process n edges: O(n × α(n))
  • Total: O(n) for practical purposes

Space Complexity: O(n)

  • Parent array: O(n)
  • Rank array: O(n)
  • Total: O(n)

Solution 2: DFS

Time Complexity: O(n)

  • Graph construction: O(n)
  • DFS traversal: O(n) - visit each node once
  • Cycle extraction: O(n) - worst case
  • Edge search: O(n) - check all edges
  • Total: O(n)

Space Complexity: O(n)

  • Adjacency list: O(n)
  • Visited array: O(n)
  • Parent array: O(n)
  • Cycle node map: O(n)
  • DFS recursion stack: O(n)
  • Total: O(n)

Key Points

  1. DSU is Optimal: Union-Find is the most efficient approach for cycle detection
  2. Path Compression: Speeds up find operations significantly
  3. Union by Rank: Keeps trees balanced for better performance
  4. 1-based to 0-based: Convert node indices when using DSU
  5. Last Edge Priority: Problem asks for last edge in input that creates cycle
  6. Single Cycle: Graph has exactly one cycle (one extra edge in tree)

Comparison: DSU vs DFS

Aspect DSU DFS
Time Complexity O(n × α(n)) ≈ O(n) O(n)
Space Complexity O(n) O(n)
Implementation Simpler More complex
Cycle Detection Direct (during union) Requires traversal
Edge Order Natural (process in order) Need to track and search
Recommended ✅ Yes ⚠️ Works but more complex

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Tags

Union-Find, DSU, Disjoint Set Union, Graph, Cycle Detection, DFS, Medium

Key Takeaways

  • Model entities as nodes and relationships as edges.
  • Pick traversal (BFS/DFS) or shortest-path (Dijkstra) based on weights.
  • Union-Find helps when connectivity updates are frequent.

References

Template Reference