Top Sort

DFS 找环模板

#include <iostream>
#include <vector>

using namespace std;

class Solution {
    vector<vector<int>> graph;
    vector<int> visited;
    bool hasCycle = true;

    void backtracking(int idx)
    {
        visited[idx] = 1; // 将节点标记为遍历中
        for (int node : graph[idx]) {
            if (visited[node] == 1) {
                // 发现环！！！
                hasCycle = false;
                return;
            } else if (visited[node] == 0) {
                backtracking(node);
            }
        }
        visited[idx] = 2; // 将节点标记为已遍历
    }

public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
    {
        graph.resize(numCourses);
        visited.resize(numCourses);
        for (auto& edge : prerequisites) {
            graph[edge[1]].emplace_back(edge[0]);
        }
				// 图中并不是所有节点都相连，所以要用一个 for 循环将所有节点都作为起点调用一次 DFS 搜索算法
        for (int i = 0; i < numCourses; i++) {
            if (!visited[i]) {
                backtracking(i);
            }
        }
        return hasCycle;
    }
};

int main(int argc, const char** argv)
{
    Solution so;
    vector<vector<int>> test = {
        { 1, 0 },
        { 0, 1 }
    };
    bool res = so.canFinish(2, test);
    return 0;
}

BFS 拓扑排序模板

class Solution {
public:
    bool
    canFinish(int numCourses, vector<vector<int>>& prerequisites)
    {
        vector<int> res;
        vector<vector<int>> graph;  // 邻接表存储有向图
        vector<int> indegree(numCourses);  // 计算各节点的入度
        graph.resize(numCourses);
        for (auto& edge : prerequisites) {
            graph[edge[1]].push_back(edge[0]);
            indegree[edge[0]]++;
        }

        queue<int> que;
        for (int i = 0; i < numCourses; i++) {
            if(indegree[i] == 0) {
                que.push(i);
            }
        }
        while (!que.empty()) {
            int root = que.front();
            res.push_back(root);
            que.pop();
            for(int node : graph[root]) {
                indegree[node]--;
                if(indegree[node] == 0) {
                    que.push(node);
                }
            }
        }
        return res.size() == numCourses;
    }
};