本题是一道拓扑排序的问题，个人感觉难度还是挺大的，即便写出来也感觉有些似懂非懂。另外我个人认为本题并没有使用传统的拓扑排序，而是通过dfs来判断的图 有没有形成环路。
本题的技巧主要是
- 把二维数组转换成类似邻接表的图的表示方法
- 深度优先搜索dfs来判断从当前顶点出发有没有形成环路。这里需要借助flag数组来进行标记，flag有3种状态，-1表有环路，0是默认值代表还未处理，1代表无环路
- 遍历所有顶点，都没有形成环路，则返回true
代码：
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& p) {
if(p.size()==0)
return true;
int n=p.size();
vector<int> flag(numCourses,0);
vector<vector<int>> tmp(numCourses,vector<int>());
for(int i=0;i<n;i++)
tmp[p[i][0]].push_back(p[i][1]);
bool ans=true;
for(int i=0;i<numCourses;i++)
ans=ans&&dfs(i,flag,tmp);
return ans;
}
bool dfs(int i,vector<int> &flag,vector<vector<int>> &tmp){
if(flag[i]==-1)
return false;
if(flag[i]==1)
return true;
flag[i]=-1;
int n=tmp[i].size();
for(int j=0;j<n;j++){
if(dfs(tmp[i][j],flag,tmp))
continue;
else
return false;
}
flag[i]=1;
return true;
}
};
预计用时10分钟，实际用时48分钟
