Redundant Connection (Find Cycle Edge)

📋

Problem

Imagine you are managing a network of computers connected by cables. You want to add cables without creating loops that cause network issues. How do you detect the first cable that creates a cycle?

Given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added, find the edge that, when added, creates a cycle. The input is a list of edges where each edge connects two nodes. Return the edge that can be removed so that the resulting graph is a tree of n nodes.

1 ≤ n ≤ 10^5edges.length == nedges[i].length == 21 ≤ edges[i][0] < edges[i][1] ≤ nNo repeated edgesThe graph is connected and has exactly one cycle

Edge cases: Minimum nodes (n=2) with one edge → output that edgeCycle formed by last edge in input → output last edgeCycle formed by an early edge → output that edge

</>

IDE

def findRedundantConnection(edges: list[list[int]]) -> list[int]:public int[] findRedundantConnection(int[][] edges)vector<int> findRedundantConnection(vector<vector<int>>& edges)function findRedundantConnection(edges)

def findRedundantConnection(edges):
    # Write your solution here
    pass

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        // Write your solution here
        return new int[0];
    }
}

#include <vector>
using namespace std;

vector<int> findRedundantConnection(vector<vector<int>>& edges) {
    // Write your solution here
    return {};
}

function findRedundantConnection(edges) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: No edge or empty listUnion-find not checking if nodes are already connected before union, so cycle edge never detected.✅ Add condition: if find(u) == find(v) return [u,v] before union operation.

Wrong: [1,2] instead of [2,3]Returning first edge instead of the first cycle edge; not checking union-find roots properly.✅ Check roots before union; only return edge if roots are same.

Wrong: Cycle edge detected late or not at allUnion-find union always performed without root check, missing early cycle edges.✅ Check if find(u) == find(v) before union; return edge if true.

Wrong: TLE on large inputUsing DFS or brute force cycle detection with O(n^2) complexity.✅ Implement union-find with path compression and union by rank for O(n α(n)) complexity.

Wrong: Wrong edge due to indexing errorsIncorrect handling of node indices or off-by-one errors in union-find.✅ Normalize indices and carefully implement find and union functions.

✓

Test Cases

Focus on handling small inputs and cycles appearing at different positions.

Watch out for common pitfalls like greedy approaches and indexing errors.

Optimize your union-find to handle large inputs efficiently.

t1_01basic

Input{"edges":[[1,2],[1,3],[2,3]]}

Expected[2,3]

⏱ Performance - must finish in 2000ms

Edges [1,2] and [1,3] form a tree. Adding [2,3] creates a cycle, so [2,3] is the redundant connection.

💡 Think about how adding edges can create cycles in a graph.

💡 Use union-find to detect when two nodes are already connected before adding an edge.

💡 Return the first edge that connects two nodes already in the same set.

Why it failed: Returned wrong edge or no edge; likely union-find not detecting cycle correctly. Fix by checking if find(u) == find(v) before union.

✓ Correctly identified the first edge that creates a cycle.

t1_02basic

Input{"edges":[[1,2],[2,3],[3,4],[1,4],[1,5]]}

Expected[1,4]

⏱ Performance - must finish in 2000ms

Edges [1,2],[2,3],[3,4] form a tree. Adding [1,4] creates a cycle, so [1,4] is the redundant connection.

💡 Track connected components as edges are added.

💡 When an edge connects nodes already in the same component, it forms a cycle.

💡 Return the first such edge encountered.

Why it failed: Incorrect cycle detection; possibly union-find union always performed without checking roots. Fix by checking roots before union.

✓ Cycle edge correctly identified in a longer chain.

t2_01edge

Input{"edges":[[1,2]]}

Expected[1,2]

⏱ Performance - must finish in 2000ms

Minimum nodes (n=2) with one edge; that edge is the redundant connection since edges.length == n.

💡 Consider the smallest graph possible with one edge.

💡 Even a single edge can form a cycle if edges.length == n.

💡 Return that edge as the redundant connection.

Why it failed: Fails on minimum input size; likely no handling for n=2 or edges.length == n. Fix by allowing single edge as cycle edge if edges length equals n.

✓ Handles minimum input size correctly.

t2_02edge

Input{"edges":[[1,2],[2,3],[3,4],[4,5],[5,1]]}

Expected[5,1]

⏱ Performance - must finish in 2000ms

Cycle formed by last edge in input; last edge closes the cycle.

💡 Check if the last edge connects nodes already connected.

💡 Union-find should detect cycle at the last edge.

💡 Return the last edge as the redundant connection.

Why it failed: Fails to detect cycle at last edge; possibly union-find not checking before union. Fix by checking roots before union operation.

✓ Correctly detects cycle formed by last edge.

t2_03edge

Input{"edges":[[1,2],[2,3],[1,3],[3,4],[4,5]]}

Expected[1,3]

⏱ Performance - must finish in 2000ms

Cycle formed by an early edge; edge [1,3] creates the cycle.

💡 Cycle can form early, not necessarily at the end.

💡 Union-find must detect cycle as soon as it appears.

💡 Return the first edge that creates a cycle.

Why it failed: Fails to detect early cycle; union-find might be delayed or incorrect. Fix by checking roots before union for every edge.

✓ Detects early cycle edge correctly.

t3_01corner

Input{"edges":[[1,2],[2,3],[3,4],[4,5],[2,5]]}

Expected[2,5]

⏱ Performance - must finish in 2000ms

Greedy trap: choosing edges without union-find can miss the first cycle edge [2,5].

💡 Greedy approaches may fail to detect cycles correctly.

💡 Use union-find to track connected components efficiently.

💡 Return the first edge that connects nodes in the same set.

Why it failed: Greedy approach returns wrong edge or no edge; fix by implementing union-find cycle detection.

✓ Union-find correctly detects cycle edge, avoiding greedy trap.

t3_02corner

Input{"edges":[[1,2],[2,3],[3,1],[1,4],[4,5]]}

Expected[3,1]

⏱ Performance - must finish in 2000ms

Off-by-one or indexing error: cycle edge [3,1] detected correctly despite node order.

💡 Check if union-find handles node indices correctly.

💡 Ensure find and union operations use correct indexing.

💡 Return the edge that closes the cycle regardless of node order.

Why it failed: Incorrect indexing causes wrong cycle detection; fix by normalizing node indices or careful union-find implementation.

✓ Correctly handles node indices and detects cycle edge.

t3_03corner

Input{"edges":[[1,2],[2,3],[3,4],[4,2],[2,5]]}

Expected[4,2]

⏱ Performance - must finish in 2000ms

Detects cycle edge in presence of multiple edges connecting same components; tests union-find correctness.

💡 Union-find must detect cycle even if cycle edge is not last.

💡 Check roots before union for every edge.

💡 Return the first edge that connects nodes in the same set.

Why it failed: Fails to detect cycle edge in middle; fix by checking roots before union for all edges.

✓ Correctly detects cycle edge in complex input.

t4_01performance

Input{"edges":[[1,2],[2,3],[3,4],[4,5],[5,6],[6,7],[7,8],[8,9],[9,10],[10,11],[11,12],[12,13],[13,14],[14,15],[15,16],[16,17],[17,18],[18,19],[19,20],[20,21],[21,22],[22,23],[23,24],[24,25],[25,26],[26,27],[27,28],[28,29],[29,30],[30,31],[31,32],[32,33],[33,34],[34,35],[35,36],[36,37],[37,38],[38,39],[39,40],[40,41],[41,42],[42,43],[43,44],[44,45],[45,46],[46,47],[47,48],[48,49],[49,50],[50,51],[51,52],[52,53],[53,54],[54,55],[55,56],[56,57],[57,58],[58,59],[59,60],[60,61],[61,62],[62,63],[63,64],[64,65],[65,66],[66,67],[67,68],[68,69],[69,70],[70,71],[71,72],[72,73],[73,74],[74,75],[75,76],[76,77],[77,78],[78,79],[79,80],[80,81],[81,82],[82,83],[83,84],[84,85],[85,86],[86,87],[87,88],[88,89],[89,90],[90,91],[91,92],[92,93],[93,94],[94,95],[95,96],[96,97],[97,98],[98,99],[99,100],[100,1]]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, edges form a cycle closing at last edge; O(n * α(n)) union-find must complete within 2s.

💡 Use union-find with path compression and union by rank for efficiency.

💡 Avoid DFS or brute force cycle detection which is O(n^2).

💡 Check roots before union to detect cycle quickly.

Why it failed: Brute force or naive union-find causes TLE; fix by implementing union-find with path compression and union by rank.

✓ Efficient union-find implementation passes performance test.

Practice

1. What is the time complexity of the optimal union-find based solution that sorts edges and processes them to remove the maximum number of edges while keeping the graph traversable for both Alice and Bob?

medium

A. O(n^2) due to checking connectivity repeatedly for each edge

B. O(m log m + m α(n)) where m is number of edges and α is inverse Ackermann function

C. O(m n) because union-find operations can be linear in worst case

D. O(m + n) since union-find operations are almost constant time

Solution

1. Step 1: Identify sorting cost

   Sorting edges costs O(m log m) where m is number of edges.

2. Step 2: Analyze union-find operations

   Union-find operations take O(α(n)) amortized per operation, so total O(m α(n)).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting dominates, union-find nearly constant -> O(m log m + m α(n)) [OK]

Hint: Sorting edges dominates complexity, union-find nearly constant [OK]

Common Mistakes:

• Assuming union-find is O(n) per operation
• Ignoring sorting cost
• Confusing n and m in complexity

2. Examine the following buggy code snippet for the optimal solution. Which line contains the subtle bug that can cause incorrect results?

medium

A. Line 2: Sorting edges by type descending

B. Line 16: Checking if both Alice and Bob are fully connected

C. Line 9: Using union-find union for type 3 edges

D. Line 6: Not adjusting node indices from 1-based to 0-based

Solution

1. Step 1: Identify indexing issue

   Input edges use 1-based node indices, but union-find expects 0-based. Missing adjustment causes wrong unions or runtime errors.

2. Step 2: Confirm other lines are correct

   Sorting edges, union calls, and connectivity checks are correct; only indexing is buggy.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing "u -= 1; v -= 1" causes incorrect unions [OK]

Hint: Check if node indices are adjusted before union-find calls [OK]

Common Mistakes:

• Ignoring 1-based to 0-based index conversion
• Misusing union-find union return value
• Skipping connectivity check for both users

3. The following code attempts to implement the optimal solution for the smallest string with swaps problem. Identify the line that contains a subtle bug that can cause incorrect output.

medium

A. Line: for i, idx in enumerate(group): res[idx] = chars[i]

B. Line: groups[uf.find(i)].append(i)

C. Line: for x, y in pairs: uf.union(x, y)

D. Line: chars.sort()

Solution

1. Step 1: Identify grouping and sorting

   Indices in each group are collected but not sorted before assignment.

2. Step 2: Check assignment order

   Assigning sorted characters to unsorted group indices causes characters to be placed incorrectly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting group indices before assignment fixes the bug [OK]

Hint: Always sort indices before assigning sorted chars [OK]

Common Mistakes:

• Not sorting indices before assignment
• Assuming group order matches index order

4. Consider the following buggy union-find code snippet for Swim in Rising Water. Which line contains the subtle bug that can cause incorrect connectivity checks?

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

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

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return false
        if self.rank[rx] <= self.rank[ry]:
            self.parent[rx] = ry
        else:
            self.parent[ry] = rx
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
        return true

medium

A. Line with 'if rx == ry: return false' (checking if already connected)

B. Line 'if self.rank[rx] <= self.rank[ry]:' (union by rank condition)

C. Line 'self.parent[rx] = ry' (assigning parent when rank comparison true)

D. Line 'if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1' (rank increment after union)

Solution

1. Step 1: Analyze union by rank condition

   The condition uses '<=' which causes incorrect parent assignment when ranks are equal.

2. Step 2: Identify correct union by rank logic

   When ranks are equal, parent of ry should be set to rx and rank of rx incremented; current code reverses this.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Incorrect rank comparison leads to wrong parent assignment [OK]

Hint: Check union by rank condition carefully for equality case [OK]

Common Mistakes:

• Misusing <= instead of < in rank comparison
• Incrementing rank of wrong root after union
• Confusing which parent to assign when ranks equal

5. Suppose the problem is modified so that stones can be removed only if they share the same row or column AND the stones are adjacent (i.e., consecutive indices in row or column). Which approach correctly adapts to this constraint?

hard

A. Use brute force DFS on the graph where edges exist only between adjacent stones in rows or columns

B. Modify union-find to only union stones if their row or column indices differ by exactly 1

C. Use the same union-find approach connecting all stones sharing rows or columns without modification

D. Sort stones and greedily remove stones from the largest connected component

Solution

1. Step 1: Understand adjacency constraint

   Only stones adjacent in row or column can be connected, so union-find on all stones sharing row/column is incorrect.

2. Step 2: Choose graph DFS on adjacency edges

   Build graph edges only between stones adjacent in row or column, then DFS to find connected components.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Union-find without adjacency check unions too many stones [OK]

Hint: Adjacency requires explicit graph edges, not union-find on all same row/col [OK]

Common Mistakes:

• Applying union-find without adjacency check
• Assuming greedy removal works
• Ignoring sorting and adjacency in graph construction