Cod sursa(job #957541)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 5 iunie 2013 12:50:12
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 50002;

typedef struct node{
    int nr, F;
};

int N, M, T;
int d[MAX_N], f[MAX_N], sol[MAX_N];
vector < int > v[MAX_N];
node a[MAX_N];

inline void DFS(int x){
    d[x] = ++T;
    for(size_t i = 0; i < v[x].size(); ++i)
        if(!d[v[x][i]])
            DFS(v[x][i]);
    f[x] = ++T;
}

inline bool cmp(node a, node b){
    return a.F > b.F;
}

int main(){
    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");

    fin >> N >> M;
    for(int i = 1, x, y; i <= N; ++i){
        fin >> x >> y;
        v[x].push_back(y);
    }

    for(int i = 1; i <= N; ++i)
        if(!d[i])
            DFS(i);
    for(int i = 1; i <= N; ++i)
        a[i].F = f[i], a[i].nr = i;
    sort(a+1, a+N+1, cmp);

    for(int i = 1; i <= N; ++i)
        fout << a[i].nr << " ";
    fout << '\n';

    fin.close();
    fout.close();

    return 0;
}