Cod sursa(job #1489683)

Utilizator serbanSlincu Serban serban Data 21 septembrie 2015 20:49:09
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>

using namespace std;

vector<int> v[50005];
int viz[50005];
int rez[50005];

void dfs(int in) {
    for(int i = 0; i < v[in].size(); i ++) {
        if(!viz[v[in][i]])
            dfs(v[in][i]);
    }
    viz[in] = true;
    rez[rez[0]] = in;
    rez[0] --;
}

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

    int n, m, x, y;
    fscanf(f, "%d %d", &n, &m);
    for(int i = 1; i <= m; i ++) {
        fscanf(f, "%d %d", &x, &y);
        v[x].push_back(y);
    }
    rez[0] = n;
    for(int i = 1; i <= n; i ++)
        if(!viz[i])
            dfs(i);

    for(int i = 1; i <= n; i ++)
        fprintf(g, "%d ", rez[i]);
    fprintf(g, "\n");
    return 0;
}