拓扑排序
标签：拓扑 back span const size else col 邻接 bsp
问题1.判断有没有环
http://hihocoder.com/problemset/problem/1174
用vector模拟邻接表，开一个记录入度的一维数组，一个存储入度为0的队列
ac代码如下
#include
#include
#include
#include
#includestring.h>
using namespace std;
typedef long long int ll;
int n,k,a,b,t,m;
const int maxn=1e5+5;
vectorint>v[maxn];
queueint>q;
int indge[maxn];
bool judge()
{
int num=0;
while(!q.empty())q.pop();
for(int i=1;i){
if(!indge[i])q.push(i);
}
while(!q.empty()){
int tot=q.front();
q.pop();
num++;
for(int i=0;i){
if(--indge[v[tot][i]]==0)q.push(v[tot][i]);
}
}
if(num==n)return true;
else return false;
}
int main()
{
cin>>t;
for(int i=1;i){
cin>>n>>m;
for(int i=0;i)v[i].clear();
memset(indge,0,sizeof(indge));
for(int j=0;j){
cin>>a>>b;
v[a].push_back(b);
indge[b]++;
}
if(judge())puts("Correct");
else puts("Wrong");
}
return 0;
}
/*
2
2 2
1 2
2 1
3 2
1 2
1 3
*/
拓扑排序
标签：拓扑 back span const size else col 邻接 bsp
原文地址：https://www.cnblogs.com/mohari/p/12895925.html
文章来自：
搜素材网的
编程语言模块，转载请注明文章出处。
文章标题：
拓扑排序
文章链接：http://soscw.com/index.php/essay/45024.html
评论