\u2714\uFE0F ***Solution - I (Multiple DFS Traversals)***\n\nThis solution is similar to that mentioned in the offical solution. We will construct the graph by adding edges one after another. After each addition of a new edge, we will do a `dfs` traversal to check if any cycle has formed. If a cycle is detected, we know that the last edge addition has led to the formation of cycle and hence we will simply return that edge.\n\n```\nvector findRedundantConnection(vector>& e) {\n\tint n = size(e);\n\tvector> graph(n+1);\n\tvector vis(n+1); \n\tfor(auto& E : e) {\n fill(begin(vis), end(vis), false); // reset the vis array\n graph[E[0]].push_back(E[1]), graph[E[1]].push_back(E[0]);\n if(dfs(graph, vis, E[0])) return E;\n }\n\treturn { }; // un-reachable\n}\nbool dfs(vector>& graph, vector& vis, int cur, int par = -1) {\n if(vis[cur]) return true; // reached already visited node - cycle detected\n vis[cur] = true;\n for(auto child : graph[cur]) \n if(child != par && dfs(graph, vis, child, cur)) return true;\n return false; // no cycle found\n}\n```\n\n***Time Complexity :*** **O(n²)**, In worst case, we may need `n` dfs calls with each taking `O(n)` time complexity.\n***Space Complexity :*** **O(n)**, to maintain `graph`\n\n---\n\n\u2714\uFE0F ***Solution - II (Single DFS Traversal)***\n\nI didn\'t get the first idea and solved the question using this solution instead. Suprisingly, I don\'t see anyone solving the question using a similar approach as this.\n\nWe need to find a cycle in the given graph and return an edge in that cycle that occurs last in input *`edges`*. We are given that a cycle always exist in the given graph and hence an answer will always exist. So, we only need to find the cycle and the edges involved in that cycle of the graph. We will store these edges in a set called *`cycle`*. \n\nFor this we can use **DFS traversal** with small modification. We will start the dfs on the given graph from node `1` and maintain a *`vis`* array denoting the nodes that are visited. We will also keep a *`par`* variable to denote the parent of current node *`cur`*. In each dfs. we will iterate over the `child` nodes of `cur`. If we ever visit an already visited node, we know that we are in a cycle. So, we will mark this node as the `cycleStart` and return. We will start pushing all nodes from the recursion stack until we reach `cycleStart` node (its first visit recursive call)\n\nWe have the following cases:\n\n1. **`child == par`** : The child node of *`cur`* is it\'s parent. So, skip it.\n2. **`cycle.empty() == true`**: We haven\'t yet detected any cycle. So we will continue exploring the graph with recursive `dfs` calls.\n3. **`cycleStart != -1`**: We have detected a cycle and marked the starting node of it. We will stop further dfs calls as cycle is found. We push all the nodes till we reach back to node numbered - `cycleStart` since they are all part of the cycle.\n4. **`cur == cycleStart`**: We have reached back to the start of cycle. By now, we have pushed all nodes in the cycle. So, just mark cycleStart as -1 denoting we don\'t need to further push any nodes and return.\n\nFinally, *`cycle`* contains all the nodes of cycle in the graph. We will iterate over the input edges in the reverse order to find the last edge in it that\'s part of cycle. If both node of an edge is in *`cycle`*, then we will return that edge.\n\n```\nunordered_set cycle; // will store all nodes of cycle\nint cycleStart = -1; // used to mark start node of cycle\nvector findRedundantConnection(vector>& e) {\n\tint n = size(e);\n\tvector> graph(n+1);\n\tvector vis(n+1); \n\t// constructing the graph from the edges\n\tfor(auto& edge : e) graph[edge[0]].push_back(edge[1]), graph[edge[1]].push_back(edge[0]);\n\tdfs(graph, vis, 1); // dfs traveral to detect cycle and fill the those nodes in cycle set.\n\tfor(int i = n-1; ~i; i--)\n\t\tif(cycle.count(e[i][0]) && cycle.count(e[i][1])) return e[i]; // last edge of input having both nodes in cycle\n\treturn { }; // un-reachable\n}\nvoid dfs(vector>& graph, vector& vis, int cur, int par = -1) {\n\tif(vis[cur]) { cycleStart = cur; return; } // reached an visited node - mark it as start of cycle and return\n\tvis[cur] = true; // not visited earlier - mark it as visited\n\tfor(auto child : graph[cur]) { // iterate over child / adjacents of current node\n\t\tif(child == par) continue; // dont visit parent again - avoids back-and-forth loop\n\t\tif(cycle.empty()) dfs(graph, vis, child, cur); // cycle not yet detected - explore graph further with dfs\n\t\tif(cycleStart != -1) cycle.insert(cur); // cycle detected - keep pushing nodes till we reach start of the cycle\n\t\tif(cur == cycleStart) { cycleStart = -1; return; } // all nodes of cycle taken - now just return\n\t}\n}\n```\n\n

\n
\n
Alternate Implementation (Faster Runtime ~4ms)
\n\n```\nint cycleStart = -1;\nbool *cycle, *vis, found{};\nvoid dfs(vector graph[], int cur, int par = -1) {\n\tif(vis[cur]) { cycleStart = cur; found = true; return; } \n\tvis[cur] = true; \n\tfor(auto child : graph[cur]) { \n\t\tif(child == par) continue; \n\t\tif(!found) dfs(graph, child, cur); \n\t\tif(cycleStart != -1) cycle[cur]=true; \n\t\tif(cur == cycleStart) { cycleStart = -1; return; } \n\t}\n}\nvector findRedundantConnection(vector>& e) {\n\tint n = size(e);\n\tvector graph[n+1];\n\tcycle = (bool*)calloc(n+1, sizeof(bool));\n vis = (bool*)calloc(n+1, sizeof(bool));\n\tfor(auto& edge : e) graph[edge[0]].push_back(edge[1]), graph[edge[1]].push_back(edge[0]);\n\tdfs(graph, 1); \n\tfor(int i = n-1; ~i; i--)\n\t\tif(cycle[e[i][0]] && cycle[e[i][1]]) return e[i]; \n\treturn { }; \n}\n```\n\n
\n

\n\n\n***Time Complexity :*** **`O(n)`**, where *`n`* is the number of nodes in the graph. We need `O(n)` for *`dfs`* and another `O(n)` for iterating through the input for finding the last edge in it that occurs in the cycle.\n***Space Complexity :*** **`O(n)`**, for maintaining *`graph`* and *`cycle`*\n\n\n---\n\n\u2714\uFE0F ***Solution - III (Union-Find)***\n\n\nWe can solve this using a Disjoint Subset Union (DSU). It involes two operations -\n* **`find(x)`**: finds the id which represents the component that a node belongs to\n* **`union(x, y)`**: joins the two components into a single component. This involves finding the representative of x-component (by `find(x)`) and y-component (by `find(y)`) and assigning them a common representative (same parent).\n\n\nWe are given various edges of the graph. These can be consider as different disconnected components. We will join these one by one. A component will be represented as a tree with all its members linked to some parent and the top parent will be considered that component\'s representative. When we find an edge that joins two nodes which are already in the same component, we will return that edge as answer. Otherwise, we will just **Union** it, i.e, connect the two components by picking that edge.\n\n```\nclass DSU {\n vector par, rank;\npublic:\n DSU(int n) : par(n), rank(n) {\n iota(begin(par), end(par), 0); // initializes each node\'s parent to be itself - fills as [0,1,2,3,...,n]\n }\n int find(int x) {\n if(x == par[x]) return x; // x is itself the parent of this component\n return find(par[x]); // recurse for parent of x\n }\n bool Union(int x, int y) {\n auto xp = find(x), yp = find(y); // find parents of x and y, i.e, representatives of components that x and y belong to\n if(xp == yp) return false; // x and y already belong to same component - not possible to union\n return par[xp] = yp; // union x and y by making parent common\n }\n // iterative implementation of find\n // int find(int x) { \n // while(x != par[x]) x = par[x];\n // return par[x];\n // }\n};\nclass Solution {\npublic:\n vector findRedundantConnection(vector>& e) {\n DSU ds(size(e)+1);\n for(auto& E : e) \n if(!ds.Union(E[0], E[1])) return E;\t// not possible to union - adding this edge was causing the cycle\n return { }; // un-reachable\n }\n};\n```\n\n---\n\n***Time Complexity :*** **O(n²)**, In this naive implementation, the worst case may lead to a scenario where we get a single component with a long lopsided chain and each `find` call will take `O(n)` for a total of `n` calls.\n***Space Complexity :*** **O(n)**, to maintain `par` array\n\n---\n\n\u2714\uFE0F ***Solution - IV (Union and Find with Path Compression)***\n\nThere\'s a very small change here from `Solution - II` in the *`find()`* function. We update the *`par[x]`* as the result returned by *`find(par[x])`* before returning from each recursive call. This will ensure that any future calls to *`find(x)`* won\'t require us to re-iterate all the way till the base `par[x]`. This effectively, **compresses the path** to parent of `x` (for future calls), as the name suggests.\n\n```\nclass DSU {\n vector par, rank;\npublic:\n DSU(int n) : par(n), rank(n) {\n iota(begin(par), end(par), 0);\n }\n int find(int x) {\n if(x == par[x]) return x; // x is itself the parent of this component\n return par[x] = find(par[x]); // update parent of x before returning for each call\n }\n bool Union(int x, int y) {\n auto xp = find(x), yp = find(y); // find parents of x and y, i.e, representatives of components that x and y belong to\n if(xp == yp) return false; // x and y already belong to same component - not possible to union\n return par[xp] = yp; // union x and y by making parent common\n }\n};\nclass Solution {\npublic:\n vector findRedundantConnection(vector>& e) {\n DSU ds(size(e)+1);\n for(auto& E : e) \n if(!ds.Union(E[0], E[1])) return E;\t// not possible to union - adding this edge was causing the cycle\n return { }; // un-reachable\n }\n};\n```\n\n***Time Complexity :*** **\u0398(nlogn)** , `find` may take `O(n)` for first few calls but since we are using path compression, each one makes subsequent searches faster and hence the amortized time complexity over a set of calls to `find` operation is `O(logn)`\n***Space Complexity :*** **O(n)**\n\n---\n\n\u2714\uFE0F ***Solution - V (Union By Rank and Find with path Compression)***\n\nThis optimization involves doing the union based on the rank (or size) of parents / representative of a component instead of just attaching one to the other randomly. This will ensure that even in the worst-case, we don\'t end up in a scenario where the *`par`* forms a skewed tree (all nodes on one-side) and we wouldn\'t need to iterate all nodes on each *`find`* call. Performing the union based on rank will keep the components/tree balanced in size.\n\n```\nclass DSU {\n vector par, rank;\npublic:\n DSU(int n) : par(n), rank(n) {\n iota(begin(par), end(par), 0);\n }\n int find(int x) {\n if(x == par[x]) return x; // x is itself the parent of this component\n return par[x] = find(par[x]); // update parent of x before returning for each call\n }\n bool Union(int x, int y) {\n int xp = find(x), yp = find(y); // find parents of x and y, i.e, representatives of components that x and y belong to\n if(xp == yp) return false; // x and y already belong to same component - not possible to union\n if(rank[xp] > rank[yp]) par[yp] = par[xp]; // union by rank - join smaller ranked to bigger one\n else if(rank[yp] > rank[xp]) par[xp] = par[yp];\n else par[xp] = yp, rank[yp]++; // same rank - join either to other and increment rank of final parent\n return true;\n }\n};\nclass Solution {\npublic:\n vector findRedundantConnection(vector>& e) {\n DSU ds(size(e) + 1);\n for(auto& E : e) \n if(!ds.Union(E[0], E[1])) return E;\t// not possible to union - adding this edge was causing the cycle\n return { }; // un-reachable\n }\n};\n```\n\n

\n
\n
Union by Size Implementation
\n\nJust using the size of trees instead of rank while doing the union. Both should give same performance on average.\n\n```\nclass DSU {\n vector par, Size;\npublic:\n DSU(int n) : par(n), Size(n,1) {\n iota(begin(par), end(par), 0);\n }\n int find(int x) {\n if(x == par[x]) return x; \n return par[x] = find(par[x]); \n }\n bool Union(int x, int y) {\n int xp = find(x), yp = find(y); \n if(xp == yp) return false; \n if(Size[xp] > Size[yp]) par[yp] = par[xp], Size[xp] += Size[yp]; // union by size\n else par[xp] = par[yp], Size[yp] += Size[xp];\n return true;\n }\n};\nclass Solution {\npublic:\n vector findRedundantConnection(vector>& e) {\n DSU ds(size(e) + 1);\n for(auto& E : e) \n if(!ds.Union(E[0], E[1])) return E;\t\n return { }; \n }\n};\n```\n\n
\n

\n\n***Time Complexity :*** **O(n*\u03B1(n)) \u2248 O(n)**, the time complexity of each `find` call after union-by-rank and path compression comes out to be `O(\u03B1(n))`, where `\u03B1(n)` is the inverse Ackermann function. It doesn\'t exceed 4 for any n < 10⁶⁰⁰ and hence is practically constant. We make `O(n)` calls in total.\n***Space Complexity :*** **O(n)**\n\n\n---\n---\n\n\uD83D\uDCBB\uD83D\uDC31\u200D\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, please do comment below \uD83D\uDC47 \n\n---\n---\n\n

Redundant Connection

Problem Description

Problem Description

Answer Panel