Cod sursa(job #690334)

Utilizator tvararuVararu Theodor tvararu Data 25 februarie 2012 15:44:41
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

int N, M;
vector<int> Start;
vector< vector<int> > listAd;
vector<bool> visited;

ofstream out ("sortaret.out");

void dfs (int nod)
{
	out << nod << ' ';
	int k = Start[nod];
	visited[nod] = true;
	
	vector<int> order;
	while (k)
	{
		if (!visited[listAd[0][k]])
		{
			order.push_back(listAd[0][k]);
			k = listAd[1][k];
		}
	}
	sort(order.begin(), order.end());
	for (unsigned i = 0; i < order.size(); i++)
		dfs (order[i]);
}

int main (int argc, char const *argv[])
{
	ifstream in ("sortaret.in");
	in >> N >> M;
	Start.resize(N + 1);
	listAd.resize(2, vector<int>(M + 1));
	for (int i = 1; i <= M; i++)
	{
		int from, to; in >> from >> to;
		listAd[0][i] = to;
		listAd[1][i] = Start[from];
		Start[from] = i;
	}
	
	/*
	for (int i = 1; i <= N; i++)
		cout << Start[i] << ' ';
	cout << '\n';
	
	for (int i = 1; i <= M; i++)
	{
		cout << listAd[0][i] << ' ' << listAd[1][i] << '\n';
	}
	*/
	
	visited.resize(N + 1);
	
	for (int i = 1; i <= N; i++)
	{
		if (!visited[i])
			dfs(i);
	}
	out.close();
	
	return 0;
}