# A completely difference approach: recursively remove leaf nodes to uncover the cycle in the graph

• Although union-find is a natural fit to this problem, I find there is another way to tackle this problem which is also intuitive and easy to understand. That is, `we can recursively remove leaf nodes from the graph to uncover the cycle existing in the graph.` A leaf node in an undirected graph is defined as `a node that is has only one adjacent neighbor.` For example, consider the following graph:

``````           1 ——— 2
\   /
3 —— 4
``````

`node 4` would be a leaf node.
Before removing the leaf node, the graph is:
1: 2, 3
2: 1,3
3: 1,2,4
4: 3
Before removing the leaf node, the graph becomes:
1: 2, 3
2: 1,3
3: 1,2

Since now the graph only contains cycle, it's straightforward to find the answer.
Below is my C++ code to implement this:

``````class Solution {
private:
void uncoverCycle(unordered_map<int, unordered_set<int>>& graph) {
int n = graph.size();
vector<int> remove = {};
for (auto& kv : graph) {
int node = kv.first;
if (adjlist.size() == 1) { // leaf node
remove.push_back(node);
graph[*it].erase(node);
}
}

if (remove.empty()) return;
else {
for (int node : remove) graph.erase(node);
uncoverCycle(graph);
}
}

public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int n = edges.size();
unordered_map<int, unordered_set<int>> graph;
for (int i = 0; i < n; ++i) { // undirected graph
graph[edges[i][0]].insert(edges[i][1]);
graph[edges[i][1]].insert(edges[i][0]);
}

// recursively remove leaf nodes to uncover the cycle
uncoverCycle(graph);

for (int i = n - 1; i >= 0; --i) {
if (graph.count(edges[i][0]) && graph.count(edges[i][1])) return edges[i];
}

return {};
}
};
``````

• Very nice solution.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.