Cod sursa(job #1455505)

Utilizator aimrdlAndrei mrdl aimrdl Data 28 iunie 2015 05:06:15
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <stdio.h>
#include <list>
#include <vector>

using namespace std;

#define NEW 0
#define WORKING 1
#define READY 2

typedef struct {
	int n;
	vector <vector <int> > vertices;
} Graph, *aGraph;

aGraph readGraph (FILE *in) {
	aGraph aG = new Graph;
	
	int n, m;
	fscanf(in, "%d %d", &n, &m);
	for (int i = 0; i < n + 1; ++i) {
		vector <int> v;
		aG->vertices.push_back(v);
	}
	
	aG->n = n;
	for (int i = 0; i < m; ++i) {
		int x, y;
		fscanf(in, "%d %d", &x, &y);
		aG->vertices[x].push_back(y);
	}
	
	return aG;
}

void dfs (aGraph aG, list <int> *l, char *nodes, int id) {
	if (nodes[id] == NEW) {
		nodes[id] = WORKING;
		for (unsigned int i = 0; i < aG->vertices[id].size(); ++i) {
			dfs(aG, l, nodes, aG->vertices[id][i]);
		}
		nodes[id] = READY;
		(*l).push_front(id);
	}
}
			
 
int main (void) {
	FILE *in = fopen("sortaret.in", "r");
	
	aGraph  aG = readGraph(in);
	fclose(in);
	
	list <int> l;	
	char *nodes = new char[aG->n + 1]();
	
	for (int i = 1; i <= aG->n; ++i) {
		dfs(aG, &l, nodes, i);
	}
	
	FILE *out = fopen("sortaret.out", "w");
	while (l.size()) {
		fprintf(out, "%d ", l.front());
		l.pop_front();
	}
	fclose(out);
	
	for (int i = 0; i < aG->n; ++i) {
		aG->vertices[i].clear();
	}
	aG->vertices.clear();
	l.clear();
	delete aG;
	delete[] nodes;
	
	return 0;
}