Cod sursa(job #2484124)

Utilizator AlexandruPaulSirbu Alex AlexandruPaul Data 30 octombrie 2019 18:16:17
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include<fstream>
#include<vector>
using namespace std;
const int Maxx=5e4+1;
vector<int> A[Maxx];
vector<int> ans;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
bool vis[Maxx];
int n,m,x,y;
void dfs(int node){
    vis[node]=1;
    vector<int>::iterator it;
    for (it=A[node].begin();it!=A[node].end();++it){
        if (!vis[(*it)]){
            dfs(*it);
        }
    }
    ans.push_back(node);
}
int main(){
    fin>>n>>m;
    for(;m;--m){
        fin>>x>>y;
        A[x].push_back(y);
    }
    int i;
    for (i=1;i<=n;++i){
        if (!vis[i]){
            dfs(i);
        }
    }
    for(i=n-1;i>=0;--i){
        fout<<ans[i]<<" ";
    }
    fout<<"\n";
    return 0;
}