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
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:\n                                 \n               1 \u2014\u2014\u2014 2 \n                \\   /\n                  3 \u2014\u2014 4\n`node 4` would be a leaf node.\nBefore removing the leaf node, the graph is:\n1: 2, 3\n2: 1,3\n3: 1,2,4\n4: 3\nBefore removing the leaf node, the graph becomes:\n1: 2, 3\n2: 1,3\n3: 1,2\n\nSince now the graph only contains cycle, it's straightforward to find the answer.\nBelow is my C++ code to implement this:\n```\nclass Solution {\nprivate:\n  void uncoverCycle(unordered_map<int, unordered_set<int>>& graph) {\n    int n = graph.size();\n    vector<int> remove = {};\n    for (auto& kv : graph) {\n      int node = kv.first;\n      auto& adjlist = kv.second;\n      if (adjlist.size() == 1) { // leaf node\n        remove.push_back(node);\n        auto it = adjlist.begin();\n        graph[*it].erase(node);\n      }\n    }\n\n    if (remove.empty()) return;\n    else {\n      for (int node : remove) graph.erase(node);\n      uncoverCycle(graph);\n    }\n  }\n\npublic:\n  vector<int> findRedundantConnection(vector<vector<int>>& edges) {\n    int n = edges.size();\n    unordered_map<int, unordered_set<int>> graph;\n    for (int i = 0; i < n; ++i) { // undirected graph\n      graph[edges[i][0]].insert(edges[i][1]);\n      graph[edges[i][1]].insert(edges[i][0]);\n    }\n\n    // recursively remove leaf nodes to uncover the cycle\n    uncoverCycle(graph);\n\n    for (int i = n - 1; i >= 0; --i) {\n      if (graph.count(edges[i][0]) && graph.count(edges[i][1])) return edges[i];\n    }\n\n    return {};\n  }\n};\n```
['Graph', 'C']