Cod sursa(job #690526)

Utilizator tvararuVararu Theodor tvararu Data 25 februarie 2012 18:19:56
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <utility>
using namespace std;

int N, M;
set< pair<int, int> > values;
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]);
			//dfs(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);
	for (int i = 1; i <= M; i++)
	{
		int from, to; in >> from >> to;
		values.insert (make_pair(from, to));
	}
	
	int count = 1;
	M = values.size();
	listAd.resize(2, vector<int>(M + 1));
	for (typeof(values.begin()) it = values.begin(); it != values.end(); it++)
	{
	//	cout << (*it).first << ' ' << (*it).second << '\n';
		listAd[0][count] = (*it).second;
		listAd[1][count] = Start[(*it).first];
		Start[(*it).first] = count;
		count++;
	}

	/*
	for (int i = 1; i <= N; i++)
		cout << Start[i] << ' ';
	cout << '\n';
	
	for (int i = 1; i <= M; i++)
	{
		cout << i << ": " << listAd[0][i] << ' ' << listAd[1][i] << '\n';
	}
	cout << '\n';
	*/
	
	visited.resize(N + 1);
	
	for (int i = 1; i <= N; i++)
	{
		if (!visited[i])
			dfs(i);
	}
	out.close();
	
	return 0;
}