Cod sursa(job #1439733)

Utilizator GeiGeiGeorge Cioroiu GeiGei Data 23 mai 2015 00:47:22
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
//004
#include <cstdio>
#include <cstdlib>
#include <list>
#define li list<long>::iterator

using namespace std;

bool adi[50000][50000];
bool ver[50000];
list<long> ord;
long n, m;

void next(long poz) {
    if (ver[poz])
        return;
    for (int j = 0; j < n; j++)
        if (adi[poz][j])
            next(j);
    ver[poz] = true;
    ord.push_front(poz + 1);
}

int main() {
    FILE* fi = fopen("sortaret.in", "rt");
    FILE* fo = fopen("sortaret.out", "wt");

    fscanf(fi, "%ld%ld", &n, &m);

    for (int i = 0; i < n; i++) {
        ver[i] = false;
        for (int j = 0; j < n; j++)
            adi[i][j] = false;
    }

    for (long i = 0; i < m; i++) {
        long a, b;
        fscanf(fi, "%ld%ld", &a, &b);
        a--; b--;
        adi[a][b] = true;
    }

    long poz = 0;
    while(poz < n) {
        if (ver[poz])
            poz++;
        else
            next(poz);
    }

    for (li it = ord.begin(); it != ord.end(); it++) {
        long aux = *it;
        fprintf(fo, "%ld ", aux);
    }

    return 0;
}