3.1 拓扑排序

有向图的存储

邻接矩阵

邻接表

拓扑排序

有向无环图：不存在环的有向图

环：
在有向图中，从一个节点出发，最终回到它自身的路径被称为环

入度：
以节点x为终点的有向边的条数被称为x的入度

出度：
以节点x为起点的有向边的条数被称为x的出度

拓扑序：

给定一张有向无环图，若一个由图中所有点构成的序列A满足：

对于图中的每条边（x，y），x在A中都出现在y之前，则称A是该有向无环图顶点的一个拓扑序。

求解序列A的过程就称为拓扑排序

例题

acwing 848 有向图的拓扑序列

题目大意：
给定一个n 个点m 条边的有向图，点的编号是1 到n ，图中可能存在重边和自环。输出其任意一个拓扑序列。如果不存在则返回− 1。

#include <bits/stdc++.h>
#define int long longusing namespace std;
const int N=2e5+10;int n,m;//n个点，m个边
int h[N],e[N],ne[N],idx;//邻接表
int d[N];//d[i]表示i的入度
int q[N];//模拟队列 拓扑序列void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}bool topsort()
{//模拟队列 hh:head tt:tailint hh=0,tt=-1;//将入度为0的节点入队,节点从1开始for(int i=1;i<=n;i++){if(d[i]==0){q[++tt]=i;}}//删边while(hh<=tt){int t=q[hh];//取出队首元素hh++;//弹出队首元素//删除t可以到达的节点for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];//取出顶点d[j]--;//删边if(d[j]==0){//如果入度为0，入队q[++tt]=j;}}}//如果可以拓扑排序返回1，否则0if(tt==n-1){return 1;}else{return 0;}
}signed main()
{cin>>n>>m;//邻接表内元素指向空集-1memset(h,-1,sizeof(h));//建图for(int i=0;i<m;i++){int a,b;cin>>a>>b;add(a,b);//b的入度+1d[b]++;}if(topsort()==0){cout<<"-1"<<endl;}else{for(int i=0;i<n;i++){cout<<q[i]<<" ";}}return 0;
}