有向图的存储
邻接矩阵
邻接表
拓扑排序
有向无环图:不存在环的有向图
环:
在有向图中,从一个节点出发,最终回到它自身的路径被称为环
入度:
以节点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;
}