Cod sursa(job #1182188)

Utilizator MarianMMorosac George Marian MarianM Data 4 mai 2014 23:51:20
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <list>
#include <iterator>
#include <algorithm>
using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

#define DMAX 11//50001

struct Graph{
	char inf[DMAX];			// content
	char color[DMAX];		// w->g->b
	int parent[DMAX], d[DMAX], f[DMAX];		// d = discovered, f = finished
	vector<int> Adj[DMAX];	// Adj list
	vector<pair<int, int>> Edge;
} G;

int N, M, time;
list<int> L;
list<int>::iterator l;

void DFS_VISIT(int root){
	int i, lg, next;

	time++;
	G.color[root] = 'g';
	G.d[root] = time;

	lg = G.Adj[root].size();
	for (i = 0; i < lg; i++){
		next = G.Adj[root][i];
		if (G.color[next] == 'w')
			DFS_VISIT(next);
	}

	time++;
	G.color[root] = 'b';
	G.f[root] = time;
	L.push_front(root);
}

void DFS(){
	int i;

	for (i = 1; i <= N; i++){
		G.color[i] = 'w';
		G.parent[i] = 0;
	}

	for (i = 1; i <= N; i++){
		if (G.color[i] == 'w'){
			DFS_VISIT(i);
		}
	}
}

int main(){
	int i, ui, vi;

	fin >> N >> M;
	for (i = 0; i < M; i++) {
		fin >> ui >> vi;
		G.Adj[ui].push_back(vi);
		G.Edge.push_back(make_pair(ui, vi));
	}

	DFS();

	for (l = L.begin(); l != L.end(); l++)	fout << *l << ' ';

	return 0;
}