Cod sursa(job #1175000)

Utilizator vlasinalinVlasin Alin vlasinalin Data 24 aprilie 2014 12:14:51
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 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[MAXNODES];
int tsorted[MAXNODES], nodes[MAXNODES], nr_of_added_nodes;
bool visited[MAXNODES];

int add_node(int node)
{
	for (int i = 0; i < nr_of_added_nodes; i++)
	{
		if (nodes[i] == node)
			return i;
	}
	nodes[nr_of_added_nodes++] = node;
	return nr_of_added_nodes - 1;
}

void read_input()
{
	string line;
	ifstream myfile("sortaret.in");
	if (myfile.is_open())
	{
		myfile >> n;
		myfile >> m;
		int i, from, to, from_index, to_index;
		for (i = 0; i < m; ++i)
		{
			myfile >> from;
			myfile >> to;

			from_index = add_node(from);
			to_index = add_node(to);
			
			adj[from_index].push_front(to_index);
			//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_index)
{
	//cout << node << ' ';
	for (int& x : adj[node_index])
	{
		if (!visited[x])
		{
			dfs(x);
		}		
	}
	visited[node_index] = true;
	tsorted[--sorted_index] = nodes[node_index];
}

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

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;
}