LeetCode 210 Course Schedule II

    
        标签：
        
            图算法
        
            LeetCode
        
    发布于：2022-02-08 18:45:14
    编辑于：2022-02-08 22:49:06
    浏览量：623

概述

https://leetcode.com/problems/course-schedule-ii/

递归法

如果不存在环，则存在可行方案，问题在于这是个图，要怎么搞好嘞。

主要是，我们要怎么处理多个可能的图和共享的节点嘞。

首先，多个可能的图既然自己相互无联系，那直接任意顺序排结果就好。

对于共享的节点，其实我们遍历的时候是作为一棵树处理的，共享节点由于被访问过，之后的访问到这里就停止了。

将后序遍历的结果进行反转，就是拓扑排序的结果。

务必注意 helper 函数里各个部分的顺序：

检查是否在路径中存在必须在检查是否访问过之前；
onPath 的设置必须在 visited 之后，否则将出现其没有被取消设置的情况。

class Solution {
public:
    vector<vector<int>> graph;
    vector<bool> onPath;
    vector<bool> visited;
    bool hasCycle = false;
    vector<int> ans;
    
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        // build graph
        vector<vector<int>> graph(numCourses);
        for (auto p : prerequisites) {
            graph[p[1]].push_back(p[0]);
        }
        this->graph = graph;
        vector<bool> onPath(numCourses, false);
        vector<bool> visited(numCourses, false);
        this->onPath = onPath;
        this->visited = visited;
        
        for (int i = 0; i < numCourses; i ++) {
            helper(i);
        }
        if (hasCycle) {
            ans.clear();
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
    
    void helper(int i) {
        if (hasCycle) return;
        if (onPath[i]) {
            hasCycle = true;
            return;
        };
        
        if (visited[i]) return;
        visited[i] = true;
        
        onPath[i] = true;
        
        for (auto n : graph[i]) {
            helper(n);
        }
        onPath[i] = false;
        ans.push_back(i);
    }
};

Links: leetcode-210-course-schedule-ii