Easy recursive cycle detection in C++


  • 0
    Y
    class Solution {
    public:
      bool canFinish(int num, vector<pair<int, int>>& pres) {
        vector<vector<int>> adj(num);
        vector<bool> visited(num, false);
        for (auto &e: pres)
          adj[e.first].push_back(e.second);
        for (int v = 0; v < num; v++)
          if (!visited[v] && hascycle(adj, visited, v))
            return false;
        return true;
      }
    private:
      bool hascycle(vector<vector<int>> &adj, vector<bool> &visited, int v) {
        visited[v] = true;
        for (int u: adj[v])
          if (visited[u] || hascycle(adj, visited, u))
            return true;
        visited[v] = false;
        return false;
      }
    };
    

Log in to reply
 

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