Cod sursa(job #1174992)

Utilizator vlasinalinVlasin Alin vlasinalin Data 24 aprilie 2014 12:03:57
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <string>
#include <forward_list>
using namespace std;

#define MAXNODES 50000
#define MAXEDGES 100000

int m, n, sorted_index;
forward_list<int> adj[MAXEDGES];
int tsorted[MAXNODES];
bool visited[MAXNODES];

void read_input()
{
	string line;
	ifstream myfile("sortaret.in");
	if (myfile.is_open())
	{
		myfile >> n;
		myfile >> m;
		int i, from, to;
		for (i = 0; i < m; ++i)
		{
			myfile >> from;
			myfile >> to;
			adj[from].push_front(to);
			//cout << a[i - 1] << ' ';
		}
		myfile.close();

		sorted_index = n;

		//for (i = 0; i < n; ++i)
		//{
		//	cout << '\n' << i << ": ";
		//	for (int& x : adj[i])
		//	{
		//		cout << x << ' ';
		//	}
		//}
	}
}

void dfs(int node)
{
	//cout << node << ' ';
	for (int& x : adj[node])
	{
		if (!visited[x])
		{
			dfs(x);
		}		
	}
	visited[node] = true;
	tsorted[--sorted_index] = node;
}

void resolve()
{
	//cout << '\n' << "dfs: ";
	dfs(1);
}

void print_solution()
{
	ofstream fout("sortaret.out");
	//cout << '\n' << "tsorted: ";
	for (int i = 0; i < n; ++i)
	{
		fout << tsorted[i] << ' ';
	}
}

int main()
{
	read_input();

	resolve();

	print_solution();

	//char x;
	//cin >> x;

	return 0;
}