Cod sursa(job #1175035)

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

#define MAXNODES 50001
#define MAXEDGES 100000

int m, n, sorted_index;
forward_list<int> adj[MAXNODES];
int tsorted[MAXNODES];
bool visited[MAXNODES], has_neigh[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);
			has_neigh[from] = true;
			has_neigh[to] = true;
		}
		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: ";
	for (int i = 1; i <= n; ++i)
	{
		if (has_neigh[i])
		{
			if (!visited[i] && !adj[i].empty())
			{
				dfs(i);
			}
		}
		else
		{
			tsorted[--sorted_index] = i;
		}
	}
}

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