An undirected graph started as a tree with N nodes labeled from 1 to N. One additional edge was added between two different nodes, creating exactly one cycle. The array edges contains all N edges in input order.
Return the last input edge eligible for removal while restoring a tree. Multiple removable edges on the cycle may exist, so preserve the input-order tie-break rule.
Example 1
Input: edges=[[1,2],[1,3],[2,3]]
Output: [2,3]
Explanation: Edge [2,3] closes cycle 1-2-3-1 and appears last among removable cycle edges.
Example 2
Input: edges=[[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]
Explanation: Edge [1,4] closes cycle 1-2-3-4-1. Removing the edge leaves a connected acyclic graph.
Brute Force Approach
Build the graph one edge at a time. Before inserting edge [u, v], search the current graph for an existing path from u to v. An existing path plus the new edge forms a cycle, making the current edge redundant.
The graph contains exactly one extra edge, so exactly one cycle exists. The first edge detected as redundant during input-order processing is the last cycle edge in input order and therefore becomes the required answer.
Algorithm
Initialize an empty adjacency list because no edges have been added.
Process every edge in the original input order, preserving the required tie break.
Run DFS from
uto check whethervis already reachable in the current graph.Return
[u, v]whenvis reachable, because the current edge closes the only cycle.Otherwise, add the edge in both directions because the graph is undirected.
Return an empty array when no cycle-closing edge exists.
Dry Run
redundant-connection-brute-force-dry-run
Solution
#include <bits/stdc++.h>using namespace std;class Solution { // Check for an existing path before adding a new edge. bool hasPath(int source, int target, const vector<vector<int>>& adjacency) { vector<int> visited(adjacency.size(), 0); stack<int> pending; pending.push(source); visited[source] = 1; // Explore the current graph with an explicit stack. while (!pending.empty()) { int node = pending.top(); pending.pop(); if (node == target) { return true; } // Add every unseen neighbor for later exploration. for (int neighbor : adjacency[node]) { if (!visited[neighbor]) { visited[neighbor] = 1; pending.push(neighbor); } } } return false; }public: // Return the edge closing the cycle. vector<int> findRedundantConnection(vector<vector<int>>& edges) { int nodes = edges.size(); vector<vector<int>> adjacency(nodes + 1); // Process edges in original input order. for (const vector<int>& edge : edges) { int first = edge[0]; int second = edge[1]; // An existing path makes the current edge redundant. if (hasPath(first, second, adjacency)) { return edge; } // Add a safe edge to the undirected graph. adjacency[first].push_back(second); adjacency[second].push_back(first); } return {}; }};// Driver code.int main() { vector<vector<int>> edges = {{1, 2}, {1, 3}, {2, 3}}; Solution sol; vector<int> answer = sol.findRedundantConnection(edges); cout << "[" << answer[0] << ", " << answer[1] << "]"; return 0;}Complexity Analysis
Time Complexity: O(N×N), where N is the number of nodes and also the number of edges in this problem; up to N DFS traversals can each process a graph of size O(N).
Space Complexity: O(N), where the adjacency list, visited array, and DFS stack store linear graph data.
Optimal Approach
Disjoint Set Union tracks the connected component containing every node. Before merging an edge, representative searches reveal whether both endpoints already belong to the same component. Equal representatives prove an existing path, so the current edge closes the cycle.
The graph contains exactly one extra edge, so the first edge having equal representatives during input-order processing is the last cycle edge in input order. Path compression and union by size keep representative searches efficient.
Algorithm
Initialize every node as an independent component with size
1.Process every edge in the original input order, preserving the required tie break.
Find the representatives of both endpoints using path compression.
Return
[u, v]when both representatives match, because the current edge closes the only cycle.Merge different representatives using union by size.
Update the surviving representative size after every successful merge.
Return an empty array only when no redundant edge exists.
Dry Run
reddxundant connections
Solution
#include <bits/stdc++.h>using namespace std;class Solution { vector<int> parent; vector<int> componentSize; // Return the representative and compress the parent path. int findParent(int node) { if (parent[node] == node) { return node; } return parent[node] = findParent(parent[node]); } // Merge two components by size and report a successful merge. bool unite(int first, int second) { int firstRoot = findParent(first); int secondRoot = findParent(second); // Equal representatives identify a cycle-forming edge. if (firstRoot == secondRoot) { return false; } // Keep the larger component as the surviving root. if (componentSize[firstRoot] < componentSize[secondRoot]) { swap(firstRoot, secondRoot); } parent[secondRoot] = firstRoot; componentSize[firstRoot] += componentSize[secondRoot]; return true; }public: // Return the edge closing the cycle. vector<int> findRedundantConnection(vector<vector<int>>& edges) { int nodes = edges.size(); parent.resize(nodes + 1); componentSize.assign(nodes + 1, 1); iota(parent.begin(), parent.end(), 0); // Process edges in original input order. for (const vector<int>& edge : edges) { if (!unite(edge[0], edge[1])) { return edge; } } return {}; }};// Driver code.int main() { vector<vector<int>> edges = {{1, 2}, {1, 3}, {2, 3}}; Solution sol; vector<int> answer = sol.findRedundantConnection(edges); cout << "[" << answer[0] << ", " << answer[1] << "]"; return 0;}Complexity Analysis
Time Complexity: O(N×α(N)), where N is the number of nodes and also the number of edges in this problem. α(N) is the inverse Ackermann function and is practically constant.
Space Complexity: O(N), where the parent and size arrays store one entry for every node.
Interview follow-up Questions
An existing path already joins both endpoints, so adding another direct edge completes a closed route.
Be the first to add a comment.