Log inSign up
mediumLeetCodeNot Started

Redundant Connection

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

Problem Statement

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.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Model cycle detection in undirected graphs using Disjoint Set Union.
  • Implement DSU with Path Compression and Union by Rank.
  • Understand why a tree on N vertices with N edges contains exactly one fundamental cycle.
  • Compare DFS cycle detection vs. DSU online edge processing.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Whenever an edge is added to an existing tree to form a single cycle, Union-Find is the classic optimal approach. The edge whose endpoints already share the same root in DSU is the cycle-closing edge.

1. DFS Reachability Check for Each Edge

Intuition

For each edge (u, v), before adding it to our growing graph, check if there is already a path from u to v using DFS. If a path already exists, adding edge (u, v) would create a cycle, making (u, v) the redundant edge. Otherwise, add (u, v) to the adjacency list and continue.

Algorithm

  1. Initialize an empty adjacency list of size n + 1.
  2. For each edge [u, v] in edges:
  3. Run dfs(u, v) on the current graph to check if v is reachable from u.
  4. If reachable:
  5. Return [u, v].
  6. Else:
  7. Add edge between u and v in adjacency list.
  8. Return empty array (fallback).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4bool dfs(int u, int target, const std::vector<std::vector<int>>& adj, std::vector<bool>& visited) {
5 if (u == target) return true;
6 visited[u] = true;
7 for (int v : adj[u]) {
8 if (!visited[v]) {
9 if (dfs(v, target, adj, visited)) return true;
10 }
11 }
12 return false;
13}
14
15std::vector<int> findRedundantConnectionDFS(std::vector<std::vector<int>>& edges) {
16 int n = edges.size();
17 std::vector<std::vector<int>> adj(n + 1);
18
19 for (const auto& e : edges) {
20 int u = e[0], v = e[1];
21 std::vector<bool> visited(n + 1, false);
22 if (dfs(u, v, adj, visited)) {
23 return e;
24 }
25 adj[u].push_back(v);
26 adj[v].push_back(u);
27 }
28 return {};
29}
30
31int main() {
32 std::vector<std::vector<int>> edges = {{1,2},{1,3},{2,3}};
33 auto res = findRedundantConnectionDFS(edges);
34 std::cout << "Redundant Edge (DFS): [" << res[0] << ", " << res[1] << "]" << std::endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(N^2) because for each of the N edges, we may explore up to N vertices via DFS.
  • Space complexity: O(N) for the adjacency list and DFS recursion stack.

2. BFS Path Check for Each Edge

Intuition

Similar to the DFS approach, but using an iterative Queue-based BFS to check if node v is already reachable from node u before inserting edge (u, v) into the graph.

Algorithm

  1. Initialize empty adjacency list for n + 1 nodes.
  2. For each edge [u, v] in edges:
  3. Run BFS from u to find v.
  4. If found, return [u, v].
  5. Else add edge to adjacency list.
  6. Return empty array.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5bool bfs(int start, int target, const std::vector<std::vector<int>>& adj, int n) {
6 std::vector<bool> visited(n + 1, false);
7 std::queue<int> q;
8 q.push(start);
9 visited[start] = true;
10
11 while (!q.empty()) {
12 int u = q.front();
13 q.pop();
14 if (u == target) return true;
15 for (int v : adj[u]) {
16 if (!visited[v]) {
17 visited[v] = true;
18 q.push(v);
19 }
20 }
21 }
22 return false;
23}
24
25std::vector<int> findRedundantConnectionBFS(std::vector<std::vector<int>>& edges) {
26 int n = edges.size();
27 std::vector<std::vector<int>> adj(n + 1);
28
29 for (const auto& e : edges) {
30 if (bfs(e[0], e[1], adj, n)) {
31 return e;
32 }
33 adj[e[0]].push_back(e[1]);
34 adj[e[1]].push_back(e[0]);
35 }
36 return {};
37}
38
39int main() {
40 std::vector<std::vector<int>> edges = {{1,2},{2,3},{3,4},{1,4},{1,5}};
41 auto res = findRedundantConnectionBFS(edges);
42 std::cout << "Redundant Edge (BFS): [" << res[0] << ", " << res[1] << "]" << std::endl;
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(N^2) as each edge check may perform an O(N) BFS traversal.
  • Space complexity: O(N) for the adjacency list and BFS queue.

3. Disjoint Set Union (DSU with Path Compression & Rank)

Intuition

Instead of searching for paths using O(N) graph traversals, use Disjoint Set Union. Each node starts in its own set. For each edge [u, v], find the root of u and the root of v. If find(u) == find(v), both vertices are already part of the same connected component, meaning adding this edge creates a cycle! Since we iterate in the order of edges, the first edge that connects two nodes with the same root is the redundant edge.

Algorithm

  1. Initialize parent array parent of size n + 1 with parent[i] = i.
  2. Initialize rank array rank of size n + 1 with 0.
  3. Define find(i) with path compression: parent[i] = find(parent[i]).
  4. Define union(i, j): attach smaller rank tree to larger rank tree.
  5. For each edge [u, v] in edges:
  6. If find(u) == find(v):
  7. Return [u, v].
  8. union(u, v).
  9. Return empty array.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4
5class DSU {
6 std::vector<int> parent, rank;
7public:
8 DSU(int n) : parent(n + 1), rank(n + 1, 0) {
9 std::iota(parent.begin(), parent.end(), 0);
10 }
11 int find(int i) {
12 if (parent[i] == i) return i;
13 return parent[i] = find(parent[i]);
14 }
15 bool unite(int i, int j) {
16 int rootI = find(i);
17 int rootJ = find(j);
18 if (rootI == rootJ) return false;
19 if (rank[rootI] < rank[rootJ]) {
20 parent[rootI] = rootJ;
21 } else if (rank[rootI] > rank[rootJ]) {
22 parent[rootJ] = rootI;
23 } else {
24 parent[rootJ] = rootI;
25 rank[rootI]++;
26 }
27 return true;
28 }
29};
30
31std::vector<int> findRedundantConnection(std::vector<std::vector<int>>& edges) {
32 int n = edges.size();
33 DSU dsu(n);
34 for (const auto& e : edges) {
35 if (!dsu.unite(e[0], e[1])) {
36 return e;
37 }
38 }
39 return {};
40}
41
42int main() {
43 std::vector<std::vector<int>> edges = {{1,2},{1,3},{2,3}};
44 auto res = findRedundantConnection(edges);
45 std::cout << "Optimal Redundant Edge: [" << res[0] << ", " << res[1] << "]" << std::endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(N * alpha(N)) where alpha is the inverse Ackermann function. Practically O(N) linear time.
  • Space complexity: O(N) auxiliary space for DSU parent and rank arrays.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.DFS Path SearchO(N^2)O(N)Simple to conceptualize using standard traversal.Performs full graph search for each edge; quadratic worst-case runtime.
2.BFS Path SearchO(N^2)O(N)Avoids call-stack depth limits.Still quadratic time due to repeated graph traversals.
3.Disjoint Set Union (DSU)OptimalO(N * alpha(N))O(N)Optimal near-linear runtime; clean online edge evaluation; no adjacency list needed.Requires implementing the Union-Find structure.

Common Pitfalls & Crucial Edge Cases

Allocating DSU arrays of size n instead of n + 1.

The nodes are 1-indexed (1 to n), so size must be at least n + 1.

Returning the first edge in the cycle rather than the last edge that appears in the input.

Processing edges in order and returning the one where find(u) == find(v) naturally returns the latest edge in the cycle.

Crucial Edge Cases to Validate:

  • Cycle involves all n nodes — The nth edge will connect the two ends of the chain and be returned.
  • n = 3 (Minimum constraint) — A triangle of 3 vertices; third edge closes the triangle and is correctly returned.
  • Large graph with n = 1000 — DSU processes all 1000 edges in less than a millisecond.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the tree edge relationship immediately: 'A tree on N nodes has N - 1 edges. Adding one edge produces exactly one cycle.'
  2. Highlight that DSU solves this in O(N * alpha(N)) time and O(N) auxiliary space without ever constructing an adjacency graph.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the graph contain exactly one cycle?

2.What is the 1-based indexing caveat in this problem?

3.If multiple edges could be removed to form a tree, which one should be returned according to the problem?

Back to DSA Sheet