如何解决hihocoder 1174 拓扑排序问题？

本文共计444个文字，预计阅读时间需要2分钟。

项目链接：拓展排序

项目大意：某些课程，某些课程是其他课程的前置技能，问题是是否所有条件都成立。

项目思路：将前置条件视为一条有向路径，所有成立的前置条件指向一个目标点，只需图中存在这样的路径即可。

题目链接：​​拓扑排序·一​​

题目大意：有一些课程，一些课是另一些课的前置技能，问是不是所有的条件都成立

题目思路：把前置条件看成一条有向路，所有的成立，只需要图中不出现环即可，拓扑排序一下，然后看是不是剩下零个点就好了

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

using namespace std;
const int maxn = 1e5+10;

vector<int>vec[maxn];
int inDeg[maxn];
int ans,T,n,m,u,v,sorted;
queue<int>q;

int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++) vec[i].clear();
memset(inDeg,0,sizeof(inDeg));
sorted = 0;
while(m--){
scanf("%d%d",&u,&v);
vec[u].push_back(v);
inDeg[v]++;
}
for(int i = 1;i <= n;i++){
if(inDeg[i] == 0) q.push(i);
}
while(!q.empty()){
int now = q.front();
q.pop();
++sorted;
for(int i = 0;i < vec[now].size();i++){
if(--inDeg[vec[now][i]] == 0) q.push(vec[now][i]);
}
}
if(sorted == n) puts("Correct");
else puts("Wrong");
}
return 0;
}