Cod sursa(job #507897)

Utilizator GodiesVlad Voicu Godies Data 7 decembrie 2010 05:23:49
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <list>

#define maxn 100000
#define maxm 50000 

using namespace std;

vector<int> *v = new vector<int> [maxn];
vector <int> colors (maxn);
list<int> final;

void dfs(int i)
{
	colors[i] = 1;
	for (size_t j = 0; j < v[i].size(); j++) {
		if (colors[v[i][j]] == 0)
			dfs(v[i][j]);
	}
	final.push_front(i);
}

int main() {
    unsigned int i, x, y, n, m;
    FILE *f = fopen("sortaret.in", "rt");
    FILE *g = fopen("sortaret.out", "wt");
    fscanf(f , "%d%d", &n, &m);
    for (i = 0; i < m; i++) {
        fscanf(f, "%d%d", &x, &y);
        v[--x].push_back(--y);
    }
    for (i = 0; i<n; i++) {
	    if (colors[i] == 0)
		    dfs(i);
    }
    for (list<int>::iterator it = final.begin(); it != final.end(); it++)
	    fprintf(g, "%d " , *it + 1);
    fclose(f);
    fclose(g);
    return 0;
}