Cod sursa(job #1160649)

Utilizator cbanu96Banu Cristian cbanu96 Data 30 martie 2014 18:04:56
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <cstdio>
#include <vector>

using namespace std;

#define FILEIN "sortaret.in"
#define FILEOUT "sortaret.out"
#define NMAX 50005

vector<int> A[NMAX];
int degIn[NMAX];
int n, m;
vector<int> sol;
int used[NMAX];

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

    sol.push_back(x);

    for ( int i = 0; i < A[x].size(); i++ ) {
        dfs(A[x][i]);
    }
}

int main() {
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    scanf("%d %d", &n, &m);
    for ( int i = 1, x, y; i <= m; i++ ) {
        scanf("%d %d", &x, &y);
        A[x].push_back(y);
        degIn[y]++;
    }

    for ( int i = 1; i <= n; i++ ) {
        if (!degIn[i])
            dfs(i);
    }

    for ( int i = 0; i < n; i++ ) {
        printf("%d ", sol[i]);
    }
    printf("\n");

    return 0;
}