拓扑排序每次输出入度为0的点,逆拓扑的思想就是每次输出出度为0的点
从入度为0的点出发dfs,每次在点出栈前输出该点,因为一个点在dfs中出栈意味着以该点为起始点所连接到的点都已经遍历过了,每遍历过一个点将这个点和与其相连的边去掉后会导致某些点出度减少,在出栈前这个点的出度就为0了
#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
int h[N],ne[N],e[N],idex;
int n,m;
bool st[N];
int r[N];
void add(int a,int b)
{
e[idex]=b;
ne[idex]=h[a];
h[a]=idex++;
}
void dfs(int a)
{
for(int i=h[a];i!=-1;i=ne[i])
{
int j=e[i];
if(!st[j])
{
st[j]=true;
dfs(j);
}
}
printf("%d ",a);
}
int main()
{
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
r[b]++;//出度加一
}
//只有从入度为0的点出发才能得到逆拓扑
for(int i=1;i<=n;i++)
if(!r[i]) dfs(i);
}
u