#include"iostream"
#include"stack"
#include"vector"
using namespace std;
vector< vector<int> > G;//采用邻接表保存图
vector<int> degree; //度数表
vector<int> is_in_stack;//判断是否入过栈
vector<int> ans; //保存答案
int n,m; //点数 弧数
int topo_sort(){
stack<int> st;
for(int i=1;i<=n;i++){ //先找到入度为0的点 压入栈中
if(degree[i]==0){
st.push(i);
is_in_stack[i] = 1; //更新点的标志
}
}
while(!st.empty()){
int now = st.top();st.pop();
ans.push_back(now);
for(int i=0;i<G[now].size();i++){//把邻接的点的度数更新
degree[G[now][i]]--;
}
for(int i=1;i<=n;i++){
if(degree[i]==0&&!is_in_stack[i]){//把更新之后的图中入度为0的点入栈
st.push(i);
is_in_stack[i]=1;
}
}
}
}
int main(){
cin>>n>>m;
G.resize(n+1);
is_in_stack.resize(n+1);
degree.resize(n+1);
for(int i=0;i<m;i++){
int st,ed;
cin>>st>>ed;
G[st].push_back(ed);
}
for(int i=1;i<=n;i++){
is_in_stack[i]=0;
for(int j=0;j<G[i].size();j++){
degree[G[i][j]]++;
}
}
topo_sort();
int first = 1;
for(int i=0;i<ans.size();i++){
if(first) {first = 0;cout<<ans[i];}
else cout<<"--->"<<ans[i];
}
cout<<endl;
return 0;
}
/*
6 8
1 2
1 3
1 4
3 2
3 5
4 5
6 4
6 5
*/
转载请注明原文地址: https://ju.6miu.com/read-970211.html
