题目链接
思路：
题目可以转换成检测一个有向图是否有环。
解法一：
深度搜索
利用着色法，对每一个节点都遍历，同时有三种遍历状态：0 未被访问，1 正被访问，2 已被访问
若在遍历时遇到正被访问的节点，说明有环。
class Solution
{
public:vector<vector<int>> graph;vector<int> color; // 0 未被访问，1 正被访问，2 已被访问bool canFinish(int numCourses, vector<vector<int>> &prerequisites){
graph.resize(numCourses);color.assign(numCourses, 0);// 构建图for (auto &edge : prerequisites)graph[edge[1]].push_back(edge[0]);// 搜索for (int i = 0; i < numCourses; i++){
if (color[i] == 0)if (!dfs(i))return false;}return true;}bool dfs(int ind){
if (color[ind] == 2)return true;color[ind] = 1;for (auto v : graph[ind]){
if (color[v] == 2)continue;if (color[v] == 1)return false;//if (color[v] == 0)if (!dfs(v))return false;}color[ind] = 2;return true;}
};
解法二：
拓扑排序
重复寻找入度为0的顶点，并将该顶点从图中删除，及其连接的所有出点入度减1，最终若图中仍存在入度为1的结点，说明有回路。
class Solution
{
public:vector<vector<int>> graph;vector<int> degree;bool canFinish(int num, vector<vector<int>> &pre){
graph.resize(num);degree.assign(num, 0);// 构建图for (auto &edge : pre){
graph[edge[1]].push_back(edge[0]);++degree[edge[0]];}// 存储所有入口点queue<int> que;for (int i = 0; i < num; i++)if (degree[i] == 0)que.push(i);while (!que.empty()){
int cur = que.front();que.pop();--num;for (auto next : graph[cur]){
if (--degree[next] == 0)que.push(next);}}return num == 0;}
};