Cod sursa(job #2484399)

Utilizator OvidRata Ovidiu Ovid Data 31 octombrie 2019 08:08:41
Problema Sortare topologica Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
ifstream fin("sortaret.in"); ofstream fout("sortaret.out");

vector<vector<int> > g;
vector<int> v;
list<int> l;
int n, m, x, y;


void dfs(int s){

if(g[s].size()==0){
    if(v[s]!=true){
l.push_front(s); cout<<s<<endl;
v[s]=true;}
}
else{
while(!g[s].empty()){
       if(v[s]!=true){dfs(g[s][0]); g[s].erase(g[s].begin());}

    }


}

}



int main(){
fin>>n>>m;
g.resize(n+1);
v.resize(n+1, 0);
for(int i=1; i<=m; i++){
fin>>x>>y;
g[x].pb(y);
}

while(l.size()<n){
for(int i=1; i<=n; i++){
    dfs(i);
} }

while(!l.empty()){
     fout<<l.front()<<' ';
     l.pop_front();
}


    return 0;
}