Cod sursa(job #1564915)

Utilizator alexarnautuArnautu Alexandru alexarnautu Data 10 ianuarie 2016 00:42:21
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <cstdio>
#include <vector>
#include <deque>
#include <bitset>
#include <algorithm>

using namespace std;

FILE * iFile;
FILE * oFile;

int nodes, edges, start;
bitset<100002> visited;
vector <int> vertices[100002];
vector <int> answer;
deque <int> que;

void read()
{
	int i, source, destination;

	fscanf(iFile, "%d %d", &nodes, &edges);

	fscanf(iFile, "%d %d", &source, &destination);

	start = source;

	vertices[source].push_back(destination);

	for(i = 1; i < edges; i++)
	{
		fscanf(iFile, "%d %d", &source, &destination);

		vertices[source].push_back(destination);
	}
}

void dfs(int start_node)
{
	int i;

	visited[start_node] = 1;
	
	for(i=0;i<vertices[start_node].size();i++)
	{
		if(visited[vertices[start_node][i]] == 0)
		{
			dfs(vertices[start_node][i]);

		}
		
	}
	answer.push_back(start_node);
}

int main()
{
	iFile = fopen("sortaret.in", "r");
	oFile = fopen("sortaret.out", "w");

	read();

	for(int i=1;i<=nodes;i++)
		if(visited[i] == 0)
			dfs(i);

	reverse(answer.begin(), answer.end());

	for(int i =0;i < answer.size(); i++)
		fprintf(oFile, "%d ", answer[i]);

	return 0;
}