保研机试备考九:拓扑排序
AcWing 848. 有向图的拓扑序列
题目
https://www.acwing.com/problem/content/850/
思路
初始化用一个数组,记录下每个点的入度。
宽搜之前把入度为0的点先入队,然后开始宽搜,把队首元素出队,相继去使它的邻接点的入度–,判断入度是否为0,为0就入队。
代码
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+10;
int n,m,x,y;
int h[N],e[N],ne[N],idx;
int q[N],hh=0,tt=-1;
int r[N];
bool st[N];
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
bool bfs()
{
for(int i=1;i<=n;i++) //扫描一遍,把入度为0的点先放到队列里面去
{
if(r[i]==0) //入度为0
{
q[++tt]=i; //入队
st[i]=true; //标记为已访问过
}
}
while(hh<=tt) //从队首元素开始出队
{
auto temp=q[hh++]; //取队首元素
for(int i=h[temp];i!=-1;i=ne[i]) //遍历它的邻接点
{
int j=e[i];
if(!st[j]) //如果没有访问过
{
r[j]--; //入度--
if(r[j]==0) //如果入度为0
{
q[++tt]=j; //入队
st[j]=true; //标记为访问过
}
}
}
}
if(tt==n-1) //如果所有的点都能入队,数组模拟队列这种思路,idx是一直递增的,能反应出多少点入过队,那直接看tt是否等于n-1,就可以判断这n个点是否都入过队了,因为第一个元素在0处
return true;
else
return false;
}
int main()
{
memset(h,-1,sizeof(h));
scanf("%d%d",&n,&m);
int a,b;
for(int i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
add(a,b);
r[b]++;
}
if(bfs())
for(int i=0;i<n;i++) printf("%d ",q[i]);
else printf("-1");
}