Share my DFS and topological sort approaches in C++


  • 1
    C

    The first approach is a depth first search cycling detection.

    class Solution {
     public:
      bool canFinish(int numCourses, 
                     const std::vector<std::pair<int, int>>& prerequisites) {
        std::vector<std::unordered_set<int>> graph;
        MakeGraph(numCourses, prerequisites, &graph);
    
        return DFS(graph);
      }
     private:
      enum VisitType {
        NotVisit = 0,
        Visited = 1,  // Ongoing DFS. If we hit this node, there is a backward edge.
        Finished = 2,  // Has finished the DFS, so the top level DFS won't visit.
      };
    
      void MakeGraph(int numCourses,
                     const std::vector<std::pair<int, int>>& prerequisites, 
                     std::vector<std::unordered_set<int>>* graph) {
        graph->resize(numCourses);
        for (const auto& prerequisit : prerequisites) {
          // The first need the second, so the representation is second -> first.
          graph->at(prerequisit.second).insert(prerequisit.first);
        }
      }
    
      bool DFS(const std::vector<std::unordered_set<int>>& graph) {
        int n_vertices = graph.size();
        std::vector<VisitType> status(n_vertices, VisitType::NotVisit);
    
        bool ret = true;
        for (int i = 0; i < n_vertices; ++i) {
          if (status[i] == VisitType::NotVisit) {
            status[i] = VisitType::Visited;
            ret = ret && DFSVisit(graph, i, &status);
          }
        }
        return ret;
      }
    
      bool DFSVisit(const std::vector<std::unordered_set<int>>& graph, int current,
                    std::vector<VisitType>* status) {
        bool ret = true;
        for (const auto& neighbor : graph[current]) {
          if (status->at(neighbor) == VisitType::Visited) return false;
    
          if (status->at(neighbor) == VisitType::NotVisit) {
            status->at(neighbor) = VisitType::Visited;
            ret = ret && DFSVisit(graph, neighbor, status);
          }
        }
        status->at(current) = VisitType::Finished;
        return ret;
      }
    };
    

    The second approach is a topological sort.

    class Solution {
     public:
      bool canFinish(int numCourses, 
                     const std::vector<std::pair<int, int>>& prerequisites) {
        std::vector<std::unordered_set<int>> graph;
        MakeGraph(numCourses, prerequisites, &graph);
    
        std::vector<int> sorted_list;
        return TopologicalSort(graph, &sorted_list);
      }
    
     private:
      void MakeGraph(int numCourses,
                     const std::vector<std::pair<int, int>>& prerequisites, 
                     std::vector<std::unordered_set<int>>* graph) {
        graph->resize(numCourses);
        for (const auto& prerequisit : prerequisites) {
          // The first need the second, so the representation is second -> first.
          graph->at(prerequisit.second).insert(prerequisit.first);
        }
      }
    
      bool TopologicalSort(const std::vector<std::unordered_set<int>>& graph,
                           std::vector<int>* sorted_list) {
        int num_node = graph.size();
        // Count indegree for each node.
        std::vector<int> indegrees(num_node, 0);
        for (int i = 0; i < num_node; ++i) {
          for (const auto& node : graph[i]) {
            ++indegrees[node];
          }
        }
    
        // Push zero indegrees to a queue.
        std::queue<int> zero_indegrees;
        for (int i = 0; i < num_node; ++i) {
          if (indegrees[i] == 0) {
            zero_indegrees.push(i);
          }
        }
    
        while (!zero_indegrees.empty()) {
          int current = zero_indegrees.front();
          sorted_list->push_back(current);
          zero_indegrees.pop();
          for (const auto& node : graph[current]) {
            --indegrees[node];
            if (indegrees[node] == 0) { 
              zero_indegrees.push(node);
            }
          }
        }
    
        for (int i = 0; i < num_node; ++i) {
          if (indegrees[i] != 0) {
            return false;
          }
        }
        return true;
      }
    };

Log in to reply
 

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