Cod sursa(job #884222)

Utilizator SmarandaMaria Pandele Smaranda Data 20 februarie 2013 19:44:15
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <cstdio>
#include <vector>

using namespace std;

const long N = 50001;
vector <long> v [N];
long t [N];
bool used [N];

void read (long &n, long &m) {
    long i, x, y;
    scanf ("%ld%ld", &n, &m);
    for (i = 0; i < m; i ++) {
        scanf ("%ld%ld", &x, &y);
        v [y].push_back (x);
    }
}

void dfs (long x) {
    vector <long> :: iterator it;
    used [x] = 1;
    for (it = v [x].begin (); it != v [x].end (); ++it)
        if (used [*it] == 0)
            dfs (*it);
    t [++ t [0]] = x;
}

int main () {
    long n, m, i;

    freopen ("sortaret.in", "r", stdin);
    freopen ("sortaret.out", "w", stdout);

    read (n, m);
    for (i = 1; i <= n; i ++)
        if (used [i] == 0)
            dfs (i);
    for (i = 1; i <= n; i ++)
        printf ("%ld ", t [i]);
    printf ("\n");
    return 0;
}