Cod sursa(job #607767)

Utilizator blustudioPaul Herman blustudio Data 13 august 2011 14:16:25
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <vector>
using namespace std;

struct node
{
	vector<unsigned long int> vertices;
	bool visited;
};

node nodes[50001];
unsigned long int n;
vector<unsigned long int> ord;
unsigned long int begin;
unsigned long int m;

void read()
{
	ifstream fin("sortaret.in");
	unsigned long int a, b;
	fin >> n >> m;
	fin >> a >> b;
	nodes[a].vertices.push_back(b);
	begin = a;
	for (unsigned long int i=2; i<=m; i++)
	{
		fin >> a >> b;
		nodes[a].vertices.push_back(b);
	}
	fin.close();
}
void bfs(unsigned long int to_visit)
{
	if (nodes[to_visit].visited == false)
	{
		ord.push_back(to_visit);
		nodes[to_visit].visited = true;
		for (unsigned long int k=0; k<nodes[to_visit].vertices.size(); k++)
		{
			bfs(nodes[to_visit].vertices[k]);
		}
	}
}
void solve()
{
	for (unsigned long int i=0; i<=n; i++)
		nodes[i].visited = false;
	bfs(begin);
	for (unsigned long int i=1; i<=n; i++)
		bfs(i);
}
void print()
{
	ofstream fout("sortaret.out");
	for (unsigned long int i=0; i<ord.size(); i++)
		fout << ord[i] << " ";
	fout.close();
}
int main()
{
	read();
	solve();
	print();
	return 0;
}