考研ds 拓扑排序+dfs逆拓扑排序
作者:
smile_922
,
2024-10-07 17:56:38
,
所有人可见
,
阅读 4
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int e[N],ne[N],h[N],idx;
int rd[N];
int n,m;
void add(int a, int b){
e[++idx]=b,ne[idx]=h[a],h[a]=idx;
}
void topsort(){
int q[N],tt=-1,hh=0;
for(int i=1;i<=n;i++){
if(!rd[i])q[++tt]=i;
}
while(hh<=tt){
int t = q[hh++];
for(int i=h[t];i;i=ne[i]){
int j = e[i];
if(--rd[j]==0)q[++tt]=j;
}
}
if(tt<n-1)cout<<-1;
else{
for(int i=0;i<=tt;i++)cout<<q[i]<<" \n"[i==tt];
}
}
bool st[N] ;
void dfs(int u){//逆拓扑排序
st[u]=true;
for(int i=h[u];i;i=ne[i]){
int j = e[i];
if(!st[j])dfs(j);
}
cout<<u<<' ';
}
int main(){
ios::sync_with_stdio(false),cin.tie(0);
cin>>n>>m;
while(m--){
int a,b;cin>>a>>b;
add(a,b);
rd[b]++;
}
topsort();
for(int i=1;i<=n;i++){
if(!st[i])dfs(i);
}
return 0;
}