Cod sursa(job #1435121)

Utilizator BFlorin93Balint Florin-Lorand BFlorin93 Data 12 mai 2015 11:09:56
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
// Toposort.cpp : Defines the entry point for the console application.
//

#include  "stdio.h"
#include "stdlib.h"
#include <iostream>
#include "vector"
#include <fstream>
#include <list>

using namespace std;

vector<int> graph[50005];
bool visited[50005];
list<int> result;

ifstream input("sortaret.in");
ofstream output("sortaret.out");

void dfs_comp(int comp);
void topoSort(int n);
void printRes();

void topoSort(int n)
{
	memset(visited, 0, (n + 1) * sizeof(bool));
	for (int i = 1; i <= n; i++)
	{
		if (!visited[i])
			dfs_comp(i);
	}
}

void dfs_comp(int comp)
{
	visited[comp] = true;
	for (int i : graph[comp])
	{
		if (!visited[i])
			dfs_comp(i);
	}
	
	result.push_front(comp);
}

void printRes()
{

	for (list<int>::iterator it = result.begin(); it != result.end(); it++)
	{
		output << *it << " ";		
	}
}

int main()
{
	int n, m;

	input >> n >> m;
	
	int x, y;
	for (int i = 0; i < m; i++)
	{
		input >> x >> y;
		graph[x].push_back(y);	
	}
	topoSort(n);
	printRes();
	input.close();
	output.close();
	return 0;
}