试题
给定一个 n 个点 m 条边的有向图,点的编号是 1 到 n,图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出 −1。
若一个由图中所有点构成的序列 A 满足:对于图中的每条边 (x,y),x 在 A 中都出现在 y 之前,则称 A 是该图的一个拓扑序列。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行,每行包含两个整数 x 和 y,表示存在一条从点 x 到点 y 的有向边 (x,y)。
输出格式
共一行,如果存在拓扑序列,则输出任意一个合法的拓扑序列即可。
否则输出 −1。
数据范围
1≤n,m≤105
输入样例:
3 3
1 2
2 3
1 3
输出样例:
1 2 3
难度:简单
时/空限制:1s / 64MB
总通过数:33126
总尝试数:51159
来源:模板题
算法标签
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010;
int h[N],e[N],ne[N],idx;
int n,m;
int q[N],d[N];//q表示队列,d表示点的入度
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];
d[j]--;//删除点t指向点j的边
if(d[j]==0)//如果点j的入度为零了,就将点j入队
q[++tt]=j;
}
}
return tt==n-1;
//表示如果n个点都入队了话,那么该图为拓扑图,返回true,否则返回false
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof(h));//如果程序时间溢出,就是没有加上这一句
for(int i=0;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);//因为是a指向b,所以b点的入度要加1
d[b]++;
}
if(topsort())
{
for(int i=0;i<n;i++)
printf("%d ",q[i]);
//经上方循环可以发现队列中的点的次序就是拓扑序列
//注:拓扑序列的答案并不唯一,可以从解析中找到解释
puts("");
}
else
puts("-1");
return 0;
}
作者:E.lena
链接:https://www.acwing.com/solution/content/21908/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
作者:E.lena
链接:https://www.acwing.com/solution/content/21908/
来源:AcWing
存在环一定不是拓扑序列 有向无环图一定存在拓扑序列
队列里的顺序就是拓扑序列
拓扑序列可能不止一种
stl法
比较麻烦需要多开一个数组储存放入队列的数和开一个变量统计放入队列数的数量
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e5+10;
int n,m;//n个点m条边
int ne[N],e[N],h[N],idx;//链表模拟4件套
int d[N];//记录每个节点的入度
int cnt;//记录储存了多少个答案
int tobe[N];//用于储存答案
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx;
idx++;
}
bool towper()
{
//初始化
queue<int>q;
for(int i=1;i<=n;i++)//注意节点编号是从1开始
{
if(d[i]==0)//将入度为0的节点如列
q.push(i);
}
while(q.size())//队列不空
{
int t=q.front();//取出对头
tobe[cnt]=t;
cnt++;
q.pop();
//拓展对头
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];//下一个节点的编号
d[j]--;//下一个节点的入度减一
if(d[j]==0)//当该节点的入度=0
q.push(j);//将该节点入列
}
}
return cnt==n;
}
int main()
{
memset(h,-1,sizeof h);//初始化头指针数组
cin>>n>>m;
for(int i=0;i<m;i++)//储存图的时候初始化入度
{
int a,b;
cin>>a>>b;
add(a,b);
d[b]++;
}
if(towper())//如果存在拓扑顺序
{
for(int i=0;i<n;i++)
{
cout<<tobe[i]<<' ';
}
}
else puts("-1");
return 0;
}
//模拟队列
#include<iostream>
#include<cstring>
using namespace std;
const int N= 1e5+10;
int e[N],ne[N],h[N],idx;//链表模拟4件套
int d[N],q[N];//d[]储存每个点的入度,q[]储存队列
int n,m;//输出的数据
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx;
idx++;
}
int toper()
{ //初始化
int tt=-1,hh=0;//队列模拟的头和尾巴
for(int i=1;i<=n;i++)
{
if(d[i]==0)//入度为0
q[++tt]=i;//队尾插入
}
while(hh<=tt)//队列不空
{
int t=q[hh++];//取出对头并删除
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];//下一个节点的编号
d[j]--;//下一个节点的入度-1
if(d[j]==0)
q[++tt]=j;//入度为0放入队列
}
}
return tt==n-1;
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);//初始化头指针数组
//储存图
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
add(a,b);
d[b]++;
}
//判断拓扑顺序并输出数据
if(toper())//yes
{
for(int i=0;i<n;i++)
cout<<q[i]<<' ';
}
else cout<<-1<<endl;
return 0;
}