文章来源:https://www.toymoban.com/news/detail-858467.html
拓扑排序的原理和宽度优先搜索差不多文章来源地址https://www.toymoban.com/news/detail-858467.html
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n,m;
int h[N],e[N],ne[N],idx;
int q[N],d[N];
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool topsort()
{
int hh=0,tt=-1;
for(int i=1;i<=n;i++)
if(!d[i]) q[++tt]=i;
while(hh<=tt)
{
int t = q[hh++];
for(int i=h[t];i!=-1;i=ne[i])
{
int j = e[i];
if(--d[j]==0)
{
q[++tt]=j;
}
}
}
return tt==n-1;
}
int main(void)
{
scanf("%d%d", &n,&m);
memset(h, -1, sizeof h);
while (m -- )
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
d[b]++;
}
if(topsort())
{
for(int i=0;i<n;i++)
printf("%d ",q[i]);
}
else puts("-1");
return 0;
}
到了这里,关于图论应用——拓扑排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!