Cod sursa(job #1750256)

Utilizator dtoniucDaniel Toniuc dtoniuc Data 29 august 2016 20:38:19
Problema Sortare topologica Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb

#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

typedef struct elem
{
	int identifier;
	struct elem* next;
} Elem;

void dfs(int, Elem**, int*, queue<int>&);

int main()
{
	ifstream fin;
	fin.open("sortaret.in");

	int N, M;
	fin >> N >> M;

	int* markList = new int[N + 1]();
	Elem** adjencyList = new Elem*[N + 1]();

	for (int i = 1; i <= M; i++)
	{
		int x, y;
		fin >> x >> y;

		Elem* newElem = new Elem();
		newElem->identifier = y;
		newElem->next = adjencyList[x];
		adjencyList[x] = newElem;

		markList[y] = 1;
	}
	fin.close();

	queue<int> result;
	for (int i = 1; i <= N; i++)
	{
		if (!markList[i])
		{
			dfs(i, adjencyList, markList, result);
		}
	}

	ofstream fout;
	fout.open("sortaret.out");
	while (!result.empty())
	{
		fout << result.front() << " ";
		result.pop();
	}
	fout.close();

	return 0;
}

void dfs(int i, Elem** adjencyList, int* markList, queue<int>& result)
{
	result.push(i);
	markList[i] = 2;

	Elem* currentElem = adjencyList[i];
	while (currentElem)
	{
		if (markList[currentElem->identifier] != 2)
		{
			dfs(currentElem->identifier, adjencyList, markList, result);
		}
		currentElem = currentElem->next;
	}
}