Cod sursa(job #851337)

Utilizator razvan.popaPopa Razvan razvan.popa Data 9 ianuarie 2013 21:17:01
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<algorithm>
#define infile "sortaret.in"
#define outfile "sortaret.out"
#define nxt (*it)
#define pb push_back
#define nMax 50005
#define FORr(g)\
   for(vector<int>::reverse_iterator it=g.rbegin(); it!=g.rend(); ++it)
#define FOR(g)\
   for(vector<int>::iterator it=g.begin(); it!=g.end(); ++it)
using namespace std;

vector < int > v[nMax], post;

bitset < nMax > used;

int N, M;


void read(){
    ifstream f(infile);

    f >> N >> M;

    int x, y;
    while(M--){
        f >> x >> y;

        v[x].pb(y);
    }

    f.close();
}

void dfs(int x){
    used[x] = true;

    FOR(v[x])
       if(!used[nxt])
          dfs(nxt);

    post.pb(x);
}

void solve(){
    for(int i=1; i<=N; ++i)
        if(!used[i])
           dfs(i);
}

void print(){
    ofstream g(outfile);

    FORr(post)
       g << nxt << " ";
    g << '\n';

    g.close();
}

int main(){
    read();
    solve();
    print();

    return 0;
}