LeetCode 210 Course Schedule II

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

概述

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

递归法

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

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

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

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

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

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

  1. 检查是否在路径中存在必须在检查是否访问过之前;
  2. 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);
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/