AcWing 848. 有向图的拓扑序列
原题链接
简单
作者:
Baitlo
,
2024-03-04 10:21:17
,
所有人可见
,
阅读 28
题解
- 有向无环图(Directed Acyclic Graph)DAG别名拓扑图,一定存在一条拓扑序列;反之,只要有向图中存在环,就肯定不存在拓扑序列。
- 每次循环查看当前图中入度为0的节点,输出它,试着去掉这个节点和其所有的边,以此类推,就可得到拓扑序列。
代码
#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>
const int N=1e6+10;
int h[N],e[N],ne[N],inx;
int d[N];//入度数组
int n,m;
int Q[N],front,rear;//队列,专门用于存放当前入度为0的点
int pr[N],p;
void add(int a,int b){//插入新节点
e[inx]=b;
ne[inx]=h[a];
h[a]=inx++;
}
bool topological(){//拓扑
for(int i=1;i<=n;i++){//把当前所有入度=0的点加入队列
if(!d[i]) Q[rear++]=i;
}
while(front<rear){
int t=Q[front++];
pr[p++]=t;
for(int i=h[t];i!=-1;i=ne[i]){//遍历所有出边
d[e[i]]--;//删除所有出边,更新入度数组
if(d[e[i]]==0) Q[rear++]=e[i];//若减为0,加入队列
}
}
if(rear!=n) return false;//若最后入队的节点数量不足,说明存在环,没有拓扑序列
return true;
}
int main(void){
cin>>n>>m;
memset(h,-1,sizeof(h));
int a,b;
for(int i=0;i<m;i++){
cin>>a>>b;
add(a,b);
d[b]++;
}
if(topological()){
for(int i=0;i<n;i++) cout<<pr[i]<<" ";
}else cout<<"-1";
}
有向图拓扑序列的个数怎么求啊
您可以思考一下,什么时候拓扑序列会从唯一的变为多条?
那就是当有一次循环发现入度为0的顶点个数不唯一,可以从多个中选一个的时候
那么若要求序列的个数,就是每次循环能找到入度为0的顶点数的乘积
比如-1个-2个-1个-3个-1个,那最后的拓扑序列的个数就是$1×2\times1\times3\times1$