Cod sursa(job #1160433)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 30 martie 2014 15:48:38
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 50002;

int N, M;
vector < int > v[MAX_N], sol;
bool m[MAX_N];

void DFS(int x) {
    m[x] = 1;

    for(int i = 0; i < (int) v[x].size(); ++i)
        if(!m[v[x][i]])
            DFS(v[x][i]);

    sol.push_back(x);
}

int main() {
    ifstream f("sortaret.in");
    ofstream g("sortaret.out");

    f >> N >> M;
    for(int i = 1, x, y; i <= M; ++i) {
        f >> x >> y;

        v[x].push_back(y);
    }

    for(int i = 1; i <= N; ++i)
        if(!m[i])
            DFS(i);
    
    reverse(sol.begin(), sol.end());
    
    for(int i = 0; i < (int) sol.size(); ++i)
        g << sol[i] << " ";
    g << "\n";

    f.close();
    g.close();

    return 0;
}