LeetCode 207 Course Schedule

    
        标签：
        
            图算法
        
            LeetCode
        
    发布于：2022-02-08 11:33:18
    编辑于：2022-02-08 18:43:47
    浏览量：839

概述

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

实际上就是有向无环图的判定。

会导致死循环的递归法

下面这个解法会导致栈溢出，因为当有环时，我们的算法就会死循环，直至堆栈溢出。

class Solution {
public:
    vector<int>* cache;
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> cache(numCourses, -1);
        this->cache = &cache;
        for (int i = 0; i < numCourses; i ++) {
            if (!isOkay(i, prerequisites)) return false;
        }
        return true;
    }
    
    bool isOkay(int i, vector<vector<int>>& prerequisites) {
        if ((*cache)[i] != -1) return (*cache)[i];
        for (auto r : prerequisites) {
            if (r[0] == i) {
                if (!isOkay(r[1], prerequisites)) {
                    (*cache)[i] = 0;
                    return false;
                }
            }
        }
        (*cache)[i] = 1;
        return true;
    }
};

图遍历法

下面这个解法会导致 TLE。

class Solution {
public:
    vector<vector<int>> graph;
    bool canFinish(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);
        for (int i = 0; i < numCourses; i ++) {
            if (!helper(i, prerequisites, onPath)) return false;
        }
        return true;
    }
    
    bool helper(int i, vector<vector<int>>& prerequisites, vector<bool>& onPath) {
        if (onPath[i]) return false;
        onPath[i] = true;
        
        for (auto n : graph[i]) {
            if (!helper(n, prerequisites, onPath)) return false;
        }
        
        onPath[i] = false;
        return true;
    }
};

实际上当我们以一个节点开始搜索是否有环时，如果该节点已经被搜索过，实际上不需要再次搜索了，就算已经历的路径不一样也没关系，因为如果后续有环的话，第一次肯定能识别到。

图遍历法（避免重复搜索）

class Solution {
public:
    vector<vector<int>> graph;
    bool hasCycle = false;
    bool canFinish(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);
        for (int i = 0; i < numCourses; i ++) {
            helper(i, prerequisites, onPath, visited);
        }
        return !hasCycle;
    }
    
    void helper(int i, vector<vector<int>>& prerequisites, vector<bool>& onPath, vector<bool>& visited) {
        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, prerequisites, onPath, visited);
        }
        
        onPath[i] = false;
    }
};

Links: leetcode-207-course-schedule