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


  • 2
    I

    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;
          auto& adjlist = kv.second;
          if (adjlist.size() == 1) { // leaf node
            remove.push_back(node);
            auto it = adjlist.begin();
            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 {};
      }
    };
    

  • 0
    P

    Very nice solution.


  • 0
    I

    @pradeepkv09 Thanks!


Log in to reply
 

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