Redundant Connection
Redundant Connection – Medium Level Problem
You are given a connected, undirected graph with n nodes labeled from 1 to n. Initially, the graph had no cycles and contained exactly n-1 edges.
Now, one extra edge has been added between two different nodes (from 1 to n) that wasn’t part of the original graph.
The graph is provided as an array edges of length n, where edges[i] = [ai, bi] represents an edge between nodes ai and bi.
What To Do ?
Your task is to return an edge that, when removed, makes the graph a connected acyclic graph.
If multiple edges can be removed, return the one that appears last in the input list.
If multiple edges can be removed, return the one that appears last in the input list.
Examples related to Redundant Connection Problem
Example 1:
Explanation:
Input:
edges = [[1,2],[1,3],[3,4],[2,4]]
Output: [2,4]
Output: [2,4]
Example 2:
Explanation:
Input:
edges = [[1,2],[1,3],[1,4],[3,4],[4,5]]
Output: [3,4]
Output: [3,4]
Constraints:
- n == edges.length
- 3 <= n <= 100
- 1 <= edges[i][0] < edges[i][1] <= edges.length
- There are no repeated edges and self loops in the input.
Hints to solve Redundant Connection Problem
Recommended Time & Space Complexity
Aim for a solution with a time complexity of O(V + E) and a space complexity of O(V + E), where V is the number of vertices and E is the number of edges.
Hint 1:
- There is only one edge that creates a cycle because the graph starts as acyclic, and the cycle forms after adding one extra edge.
- Can you think of an algorithm to detect if the current edge creates a cycle? Consider using a component-based approach.
Hint 2:
The Union-Find (Disjoint Set Union) algorithm can be used to process the edges.
While connecting edges, if an edge cannot be connected (indicating it forms a cycle), that edge is the redundant one, and we return it.
How would you design this?
Hint 3:
- Initialize a DSU object and iterate through the edges. For each edge, use the union function to connect the nodes.
- If the union function fails (returns false), it means the current edge forms a cycle, and that edge is the answer.
Methods to Solve Redundant Connection Problem
There are mainly 4 approaches to solve Redundant Connection Problem:
- Cycle Detection (DFS)
- Depth First Search (Optimal)
- Topological Sort (Kahn’s Algorithm)
- Disjoint Set Union
1. Cycle Detection (DFS) Method
Use Depth First Search to explore the graph and check for cycles. If adding an edge forms a cycle, that edge is redundant and should be removed.
- Time complexity: O(E∗(V+E))
- Space complexity: O(V+E)
Where V is the number of vertices and E is the number of edges.
Code:
C++
Java
Python
JavaScript
C++
class Solution {
public:
vector<int>
findRedundantConnection(vector<vector<int>>& edges) {
int n = edges.size();
vector<vector> adj(n + 1);
for (const auto& edge : edges) {
int u = edge[0], v = edge[1];
adj[u].push_back(v);
adj[v].push_back(u);
vector visit(n + 1, false);
if (dfs(u, -1, adj, visit)) {
return {u, v};
}
}
return {};
}
private:
bool dfs(int node, int parent,
vector<vector<int>>& adj, vector<bool>& visit) {
if (visit[node]) return true;
visit[node] = true;
for (int nei : adj[node]) {
if (nei == parent) continue;
if (dfs(nei, node, adj, visit)) return true;
}
return false;
}
};
Java
public class Solution {
public int[] findRedundantConnection(int[][] edges) {
int n = edges.length;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i <= n; i++) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
int u = edge[0], v = edge[1];
adj.get(u).add(v);
adj.get(v).add(u);
boolean[] visit = new boolean[n + 1];
if (dfs(u, -1, adj, visit)) {
return edge;
}
}
return new int[0];
}
private boolean dfs(int node, int parent,
List<List<Integer>> adj, boolean[] visit) {
if (visit[node]) {
return true;
}
visit[node] = true;
for (int nei : adj.get(node)) {
if (nei == parent) {
continue;
}
if (dfs(nei, node, adj, visit)) {
return true;
}
}
return false;
}
}
Python
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
n = len(edges)
adj = [[] for _ in range(n + 1)]
def dfs(node, par):
if visit[node]:
return True
visit[node] = True
for nei in adj[node]:
if nei == par:
continue
if dfs(nei, node):
return True
return False
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
visit = [False] * (n + 1)
if dfs(u, -1):
return [u, v]
return []
JavaScript
class Solution {
/**
* @param {number[][]} edges
* @return {number[]}
*/
findRedundantConnection(edges) {
const n = edges.length;
const adj = Array.from({ length: n + 1 }, () => []);
const dfs = (node, parent, visited) => {
if (visited[node]) return true;
visited[node] = true;
for (const nei of adj[node]) {
if (nei === parent) continue;
if (dfs(nei, node, visited)) return true;
}
return false;
};
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
const visited = Array(n + 1).fill(false);
if (dfs(u, -1, visited)) {
return [u, v];
}
}
return [];
}
}
2. Depth First Search (Optimal)
Traverse the graph using DFS while keeping track of visited nodes. If revisiting a node through an already visited path, the edge causing the revisit is the redundant one.
- Time complexity: O(V + E)
- Space complexity: O(V + E)
Where V is the number of vertices and E is the number of edges.
Code:
C++
Java
Python
JavaScript
C++
class Solution {
vector<bool> visit;
vector<vector<int>> adj;
unordered_set<int> cycle;
int cycleStart;
public:
vector<int>
findRedundantConnection(vector<vector<int>>& edges) {
int n = edges.size();
adj.resize(n + 1);
for (auto& edge : edges) {
int u = edge[0], v = edge[1];
adj[u].push_back(v);
adj[v].push_back(u);
}
visit.resize(n + 1, false);
cycleStart = -1;
dfs(1, -1);
for (int i = edges.size() - 1; i >= 0; i--) {
int u = edges[i][0], v = edges[i][1];
if (cycle.count(u) && cycle.count(v)) {
return {u, v};
}
}
return {};
}
private:
bool dfs(int node, int par) {
if (visit[node]) {
cycleStart = node;
return true;
}
visit[node] = true;
for (int nei : adj[node]) {
if (nei == par) continue;
if (dfs(nei, node)) {
if (cycleStart != -1) cycle.insert(node);
if (node == cycleStart) {
cycleStart = -1;
}
return true;
}
}
return false;
}
};
Java
public class Solution {
private boolean[] visit;
private List<List<Integer>> adj;
private Set<Integer> cycle;
private int cycleStart;
public int[] findRedundantConnection(int[][] edges) {
int n = edges.length;
adj = new ArrayList<>();
for (int i = 0; i <= n; i++)
adj.add(new ArrayList<>());
for (int[] edge : edges) {
int u = edge[0], v = edge[1];
adj.get(u).add(v);
adj.get(v).add(u);
}
visit = new boolean[n + 1];
cycle = new HashSet<>();
cycleStart = -1;
dfs(1, -1);
for (int i = edges.length - 1; i >= 0; i--) {
int u = edges[i][0], v = edges[i][1];
if (cycle.contains(u) && cycle.contains(v)) {
return new int[]{u, v};
}
}
return new int[0];
}
private boolean dfs(int node, int par) {
if (visit[node]) {
cycleStart = node;
return true;
}
visit[node] = true;
for (int nei : adj.get(node)) {
if (nei == par) continue;
if (dfs(nei, node)) {
if (cycleStart != -1) cycle.add(node);
if (node == cycleStart) {
cycleStart = -1;
}
return true;
}
}
return false;
}
}
Python
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
n = len(edges)
adj = [[] for _ in range(n + 1)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
visit = [False] * (n + 1)
cycle = set()
cycleStart = -1
def dfs(node, par):
nonlocal cycleStart
if visit[node]:
cycleStart = node
return True
visit[node] = True
for nei in adj[node]:
if nei == par:
continue
if dfs(nei, node):
if cycleStart != -1:
cycle.add(node)
if node == cycleStart:
cycleStart = -1
return True
return False
dfs(1, -1)
for u, v in reversed(edges):
if u in cycle and v in cycle:
return [u, v]
return []
JavaScript
class Solution {
/**
* @param {number[][]} edges
* @return {number[]}
*/
findRedundantConnection(edges) {
const n = edges.length;
const adj = Array.from({ length: n + 1 }, () => []);
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
}
const visit = Array(n + 1).fill(false);
const cycle = new Set();
let cycleStart = -1;
const dfs = (node, par) => {
if (visit[node]) {
cycleStart = node;
return true;
}
visit[node] = true;
for (const nei of adj[node]) {
if (nei === par) continue;
if (dfs(nei, node)) {
if (cycleStart !== -1) cycle.add(node);
if (node === cycleStart) {
cycleStart = -1;
}
return true;
}
}
return false;
};
dfs(1, -1);
for (let i = edges.length - 1; i >= 0; i--) {
const [u, v] = edges[i];
if (cycle.has(u) && cycle.has(v)) {
return [u, v];
}
}
return [];
}
}
3. Topological Sort (Kahn’s Algorithm)
Leverage Kahn’s Algorithm to maintain a topological order of the graph. The edge causing a cycle during this process is identified as redundant.
- Time complexity: O(V+E)
- Space complexity: O(V+E)
Where V is the number of vertices and E is the number of edges.
Code:
C++
Java
Python
JavaScript
C++
class Solution {
public:
vector<int>
findRedundantConnection(vector<vector<int>>& edges) {
int n = edges.size();
vector<int> indegree(n + 1, 0);
vector<vector<int>> adj(n + 1);
for (auto& edge : edges) {
int u = edge[0], v = edge[1];
adj[u].push_back(v);
adj[v].push_back(u);
indegree[u]++;
indegree[v]++;
}
queue<int> q;
for (int i = 1; i <= n; i++) { if (indegree[i] == 1) q.push(i); } while (!q.empty()) { int node = q.front(); q.pop(); indegree[node]--; for (int nei : adj[node]) { indegree[nei]--; if (indegree[nei] == 1) q.push(nei); } } for (int i = edges.size() - 1; i >= 0; i--) {
int u = edges[i][0], v = edges[i][1];
if (indegree[u] == 2 && indegree[v])
return {u, v};
}
return {};
}
};
Java
public class Solution {
public int[] findRedundantConnection(int[][] edges) {
int n = edges.length;
int[] indegree = new int[n + 1];
List<List<Integer>> adj = new ArrayList<>(n + 1);
for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
for (int[] edge : edges) {
int u = edge[0], v = edge[1];
adj.get(u).add(v);
adj.get(v).add(u);
indegree[u]++;
indegree[v]++;
}
Queue q = new LinkedList<>();
for (int i = 1; i <= n; i++) { if (indegree[i] == 1) q.offer(i); } while (!q.isEmpty()) { int node = q.poll(); indegree[node]--; for (int nei : adj.get(node)) { indegree[nei]--; if (indegree[nei] == 1) q.offer(nei); } } for (int i = edges.length - 1; i >= 0; i--) {
int u = edges[i][0], v = edges[i][1];
if (indegree[u] == 2 && indegree[v] > 0)
return new int[]{u, v};
}
return new int[0];
}
}
Python
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
n = len(edges)
indegree = [0] * (n + 1)
adj = [[] for _ in range(n + 1)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
indegree[u] += 1
indegree[v] += 1
q = deque()
for i in range(1, n + 1):
if indegree[i] == 1:
q.append(i)
while q:
node = q.popleft()
indegree[node] -= 1
for nei in adj[node]:
indegree[nei] -= 1
if indegree[nei] == 1:
q.append(nei)
for u, v in edges[::-1]:
if indegree[u] == 2 and indegree[v]:
return [u, v]
return []
JavaScript
class Solution {
/**
* @param {number[][]} edges
* @return {number[]}
*/
findRedundantConnection(edges) {
const n = edges.length;
const indegree = new Array(n + 1).fill(0);
const adj = Array.from({ length: n + 1 }, () => []);
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
indegree[u]++;
indegree[v]++;
}
const q = new Queue();
for (let i = 1; i <= n; i++) { if (indegree[i] === 1) q.push(i); } while (!q.isEmpty()) { const node = q.pop(); indegree[node]--; for (const nei of adj[node]) { indegree[nei]--; if (indegree[nei] === 1) q.push(nei); } } for (let i = edges.length - 1; i >= 0; i--) {
const [u, v] = edges[i];
if (indegree[u] === 2 && indegree[v])
return [u, v];
}
return [];
}
}
4. Disjoint Set Union
Use DSU to manage connected components. When an edge connects nodes already in the same component, it indicates a cycle, and the edge is redundant.
- Time complexity: O(V+(E∗α(V)))
- Space complexity: O(V)
Where V is the number of vertices and E is the number of edges.
Code:
C++
Java
Python
JavaScript
C++
class Solution {
public:
vector<int>
findRedundantConnection(vector<vector<int>>& edges) {
int n = edges.size();
vector<int> par(n + 1), rank(n + 1, 1);
for (int i = 0; i <= n; ++i)
par[i] = i;
for (const auto& edge : edges) {
if (!Union(par, rank, edge[0], edge[1]))
return vector<int>{ edge[0], edge[1] };
}
return {};
}
private:
int Find(vector<int>& par, int n) {
int p = par[n];
while (p != par[p]) {
par[p] = par[par[p]];
p = par[p];
}
return p;
}
bool Union(vector<int>& par, vector<int>& rank, int n1, int n2) {
int p1 = Find(par, n1);
int p2 = Find(par, n2);
if (p1 == p2)
return false;
if (rank[p1] > rank[p2]) {
par[p2] = p1;
rank[p1] += rank[p2];
} else {
par[p1] = p2;
rank[p2] += rank[p1];
}
return true;
}
};
Java
public class Solution {
public int[] findRedundantConnection(int[][] edges) {
int[] par = new int[edges.length + 1];
int[] rank = new int[edges.length + 1];
for (int i = 0; i < par.length; i++) {
par[i] = i;
rank[i] = 1;
}
for (int[] edge : edges) {
if (!union(par, rank, edge[0], edge[1]))
return new int[]{edge[0], edge[1]};
}
return new int[0];
}
private int find(int[] par, int n) {
int p = par[n];
while (p != par[p]) {
par[p] = par[par[p]];
p = par[p];
}
return p;
}
private boolean union(int[] par, int[] rank, int n1, int n2) {
int p1 = find(par, n1);
int p2 = find(par, n2);
if (p1 == p2)
return false;
if (rank[p1] > rank[p2]) {
par[p2] = p1;
rank[p1] += rank[p2];
} else {
par[p1] = p2;
rank[p2] += rank[p1];
}
return true;
}
}
Python
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
par = [i for i in range(len(edges) + 1)]
rank = [1] * (len(edges) + 1)
def find(n):
p = par[n]
while p != par[p]:
par[p] = par[par[p]]
p = par[p]
return p
def union(n1, n2):
p1, p2 = find(n1), find(n2)
if p1 == p2:
return False
if rank[p1] > rank[p2]:
par[p2] = p1
rank[p1] += rank[p2]
else:
par[p1] = p2
rank[p2] += rank[p1]
return True
for n1, n2 in edges:
if not union(n1, n2):
return [n1, n2]
JavaScript
class Solution {
/**
* @param {number[][]} edges
* @return {number[]}
*/
findRedundantConnection(edges) {
const par = new Array(edges.length + 1).fill(0).map((_, i) => i);
const rank = new Array(edges.length + 1).fill(1);
/**
* @param {number} n
* @return {number}
*/
function find(n) {
let p = par[n];
while (p !== par[p]) {
par[p] = par[par[p]];
p = par[p];
}
return p;
}
/**
* @param {number} n1
* @param {number} n2
* @return {boolean}
*/
function union(n1, n2) {
const p1 = find(n1);
const p2 = find(n2);
if (p1 === p2) {
return false;
}
if (rank[p1] > rank[p2]) {
par[p2] = p1;
rank[p1] += rank[p2];
} else {
par[p1] = p2;
rank[p2] += rank[p1];
}
return true;
}
for (const [n1, n2] of edges) {
if (!union(n1, n2)) {
return [n1, n2];
}
}
return [];
}
}
