Cod sursa(job #1993894)

Utilizator teo.cons98Constantin Teodor-Claudiu teo.cons98 Data 23 iunie 2017 22:57:10
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

unsigned int nrNoduri, nrMuchii, nodPlecare;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

vector < vector <unsigned int> > A;

vector < pair < unsigned int, unsigned int > > trecere;

vector <int> parcurgere;

int k = 1;

vector <bool> verif;

unsigned int complet = 0;

unsigned int b;

void citire()
{
	int a, b;
	fin >> nrNoduri >> nrMuchii;
	A.resize(nrNoduri + 1);
	trecere.resize(nrNoduri + 1);
	verif.resize(nrNoduri + 1);
	parcurgere.resize((nrNoduri + 1) * 2);

	for (int i = 0; i < nrMuchii; ++i)
	{
		fin >> a >> b;
		A[a].push_back(b);
		verif[b] = 1;
	}
}

void functie(int x)
{
	int b;
	trecere[x].first = k;
	parcurgere[k] = x;
	++k;
	for (int i = 0; i < A[x].size(); ++i)
	{
		b = A[x][i];
		if (verif[b] == 0)
		{
			functie(b);
		}
	}

	trecere[x].second = k;
	parcurgere[k] = x;
	++k;
	verif[x] = 1;

}

int main()
{
	citire();
	for (int i = 1; i <= nrNoduri; ++i)
	{
		if (verif[i] == 0)
		{
			nodPlecare = i;
			break;
		}
	}

	for (int i = 1; i <= nrNoduri; ++i)
	{
		verif[i] = 0;
	}

	functie(nodPlecare);

	for (int i = 1; i <= nrNoduri; ++i)
	{
		verif[i] = 0;
	}

	for (int i = 2 * nrNoduri; i > 0 && complet < nrNoduri; --i)
	{
		b = parcurgere[i];
		if (verif[b] == 0)
		{
			verif[b] = 1;
			fout << b << " ";
			complet++;
		}
	}

	while (true)
	{

	}

}