环检测及拓扑排序算法

// 函数签名如下
bool canFinish(int numCourses, vector<vector<int>>& prerequisites);

vector<vector<int>> buildGraph(int numCourses, vector<vector<int>>& prerequisites) {
    // 图中共有 numCourses 个节点
    vector<vector<int>> graph(numCourses);
    for (int i = 0; i < numCourses; i++) {
        graph[i] = vector<int>();
    }
    for (auto& edge : prerequisites) {
        int from = edge[1], to = edge[0];
        // 添加一条从 from 指向 to 的有向边
        // 边的方向是「被依赖」关系，即修完课程 from 才能修课程 to
        graph[from].push_back(to);
    }
    return graph;
}

class Solution {
public:
    // 记录递归堆栈中的节点
    vector<bool> onPath;
    // 记录图中是否有环
    bool hasCycle = false;

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph = buildGraph(numCourses, prerequisites);
        
        onPath = vector<bool>(numCourses);
        
        for (int i = 0; i < numCourses; i++) {
            // 遍历图中的所有节点
            traverse(graph, i);
        }
        // 只要没有循环依赖可以完成所有课程
        return !hasCycle;
    }

    // 图遍历函数，遍历所有路径
    void traverse(vector<vector<int>>& graph, int s) {
        if (hasCycle) {
            // 如果已经找到了环，也不用再遍历了
            return;
        }

        if (onPath[s]) {
            // s 已经在递归路径上，说明成环了
            hasCycle = true;

            return;
        }
        
        // 前序代码位置
        onPath[s] = true;
        for (int t : graph[s]) {
            traverse(graph, t);
        }
        // 后序代码位置
        onPath[s] = false;
    }

    vector<vector<int>> buildGraph(int numCourses, vector<vector<int>>& prerequisites) {
        // 代码见前文
    }
};

class Solution {
public:
    // 记录一次递归堆栈中的节点
    vector<bool> onPath;
    // 记录节点是否被遍历过
    vector<bool> visited;
    // 记录图中是否有环
    bool hasCycle = false;

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        auto graph = buildGraph(numCourses, prerequisites);
        
        onPath = vector<bool>(numCourses);
        visited = vector<bool>(numCourses);
        
        for (int i = 0; i < numCourses; i++) {
            // 遍历图中的所有节点
            traverse(graph, i);
        }
        // 只要没有循环依赖可以完成所有课程
        return !hasCycle;
    }

    // 图遍历函数，遍历所有路径
    void traverse(vector<vector<int>>& graph, int s) {
        if (hasCycle) {
            // 如果已经找到了环，也不用再遍历了
            return;
        }

        if (onPath[s]) {
            // s 已经在递归路径上，说明成环了
            hasCycle = true;

            return;
        }
        
        if (visited[s]) {
            // 不用再重复遍历已遍历过的节点
            return;
        }

        if (hasCycle) {
            // 如果已经找到了环，也不用再遍历了
            return;
        }

        // 前序代码位置
        visited[s] = true;
        onPath[s] = true;
        for (int t : graph[s]) {
            traverse(graph, t);
        }
        // 后序代码位置
        onPath[s] = false;
    }

    vector<vector<int>> buildGraph(int numCourses, vector<vector<int>>& prerequisites) {
        // 代码见前文
    }
};

vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites);

vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    if (!canFinish(numCourses, prerequisites)) {
        // 不可能完成所有课程
        return vector<int>();
    }
    // ...
}

class Solution {
public:
    // 记录后序遍历结果
    vector<int> postorder;
    // 记录是否存在环
    bool hasCycle = false;
    vector<bool> visited, onPath;

    // 主函数
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int>* graph = buildGraph(numCourses, prerequisites);
        visited = vector<bool>(numCourses);
        onPath = vector<bool>(numCourses);
        // 遍历图
        for (int i = 0; i < numCourses; i++) {
            traverse(graph, i);
        }
        // 有环图无法进行拓扑排序
        if (hasCycle) {
            return vector<int>();
        }
        // 逆后序遍历结果即为拓扑排序结果
        reverse(postorder.begin(), postorder.end());
        return postorder;
    }

    // 图遍历函数
    void traverse(vector<int>* graph, int s) {
        if (onPath[s]) {
            // 发现环
            hasCycle = true;
        }
        if (visited[s] || hasCycle) {
            return;
        }
        // 前序遍历位置
        onPath[s] = true;
        visited[s] = true;
        for (int t : graph[s]) {
            traverse(graph, t);
        }
        // 后序遍历位置
        postorder.push_back(s);
        onPath[s] = false;
    }

    // 建图函数
    vector<int> buildGraph(int numCourses, vector<vector<int>>& prerequisites) {
        // 代码见前文
    }
};

void traverse(TreeNode* root) {
    // 前序遍历代码位置
    traverse(root->left);
    // 中序遍历代码位置
    traverse(root->right);
    // 后序遍历代码位置
}

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // 建图，有向边代表「被依赖」关系
        vector<int>* graph = buildGraph(numCourses, prerequisites);
        // 构建入度数组
        vector<int> indegree(numCourses);
        for (auto& edge : prerequisites) {
            int from = edge[1], to = edge[0];
            // 节点 to 的入度加一
            indegree[to]++;
        }

        // 根据入度初始化队列中的节点
        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                // 节点 i 没有入度，即没有依赖的节点
                // 可以作为拓扑排序的起点，加入队列
                q.push(i);

            }
        }

        // 记录遍历的节点个数
        int count = 0;
        // 开始执行 BFS 循环
        while (!q.empty()) {
            // 弹出节点 cur，并将它指向的节点的入度减一
            int cur = q.front();
            q.pop();
            count++;
            for (int next : graph[cur]) {

                indegree[next]--;
                if (indegree[next] == 0) {
                    // 如果入度变为 0，说明 next 依赖的节点都已被遍历
                    q.push(next);
                }
            }
        }

        // 如果所有节点都被遍历过，说明不成环
        return count == numCourses;
    }

    // 建图函数
    vector<int>* buildGraph(int n, vector<vector<int>>& edges) {
        // 见前文
    }
};

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        // 建图，和环检测算法相同
        vector<vector<int>> graph = buildGraph(numCourses, prerequisites);
        // 计算入度，和环检测算法相同
        vector<int> indegree(numCourses);
        
        for (vector<int> edge : prerequisites) {
            int from = edge[1], to = edge[0];
            indegree[to]++;
        }

        // 根据入度初始化队列中的节点，和环检测算法相同
        queue<int> q;
        
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                q.push(i);

            }
        }

        // 记录拓扑排序结果
        vector<int> res(numCourses);
        
        // 记录遍历节点的顺序（索引）
        int count = 0;
        
        // 开始执行 BFS 算法
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            
            // 弹出节点的顺序即为拓扑排序结果
            res[count] = cur;
            count++;
            
            for (int next : graph[cur]) {

                indegree[next]--;
                if (indegree[next] == 0) {
                    q.push(next);
                }
            }
        }

        if (count != numCourses) {
            // 存在环，拓扑排序不存在
            return {};
        }
        
        return res;
    }

private:
    vector<vector<int>> buildGraph(int n, vector<vector<int>>& edges) {
        // 见前文
    }
};