Cod sursa(job #1223302)

Utilizator mucenic_b101Bogdan Mucenic mucenic_b101 Data 26 august 2014 15:30:30
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <cstdio>
#include <vector>

#define MAXN 50000
#define MAXM 100000
#define pb push_back

using namespace std;

vector <int> G[MAXN+1];
int stack[MAXN+1];
bool mark[MAXN+1];

void DFS(int node) {
    mark[node] = true;

    for (int i = 0 ; i < G[node].size() ; ++i)
        if (!mark[G[node][i]])
            DFS(G[node][i]);

    stack[++stack[0]] = node;
}

int main() {
    FILE *f, *g;
    f = fopen("sortaret.in", "r");
    g = fopen("sortaret.out", "w");

    int n, m, x, y;

    fscanf(f, "%d%d", &n, &m);

    for (int i = 0 ; i < m ; ++i) {
        fscanf(f, "%d%d", &x, &y);
        G[x].pb(y);
    }

    DFS(1);

    for (int i = n ; i >= 1 ; --i)
        fprintf(g, "%d\n", stack[i]);

    fclose(f);
    fclose(g);

    return 0;
}