Cod sursa(job #442835)

Utilizator digistyl3Janos Levai digistyl3 Data 15 aprilie 2010 15:21:14
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
/* 
 * File:   main.cpp
 * Author: Johnny
 *
 * Created on April 15, 2010, 2:59 PM
 */

#include <stdlib.h>
#include <list>
#include <stdio.h>
using namespace std;

#define MAXN 50000

list<int> rel[MAXN];
list<int> res;
bool was[MAXN];

void depth_first(int node);

int main(int argc, char** argv) {
    int n, m;
    int x, y;

    FILE * f = fopen("sortaret.in", "r");
    fscanf(f, "%d %d", &n, &m);
    for (int i = 0; i < m; ++i) {
        fscanf(f, "%d %d", &x, &y);
        rel[x - 1].push_front(y - 1);
    }
    fclose(f);

    for (int i = 0; i < n; ++i)
        if (!was[i])
            depth_first(i);

    f = fopen("sortaret.out", "w");
    for (list<int>::iterator it = res.begin(); it != res.end(); it++)
        fprintf(f, "%d ", *it + 1); 
    fclose(f);

    return (EXIT_SUCCESS);
}

void depth_first(int node) {
    was[node] = true;
    for (list<int>::iterator it = rel[node].begin(); it != rel[node].end(); it++)
        if (!was[*it])
            depth_first(*it);
    res.push_front(node);
}