Cod sursa(job #1994099)

Utilizator teo.cons98Constantin Teodor-Claudiu teo.cons98 Data 24 iunie 2017 10:53:12
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

unsigned int nrNoduri, nrMuchii, nodPlecare;

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

vector <unsigned int> A[50001];

pair < unsigned int, unsigned int > trecere[50001];

int parcurgere[100005];

int k = 1;

bool verif[50001], verif2[50001];

unsigned int complet = 0;

unsigned int b;

void citire()
{
	int a, b;
	fin >> nrNoduri >> nrMuchii;

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

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

}

int main()
{
	citire();

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

	for (unsigned int i = 1; i <= nrNoduri; ++i)
	{
		if (verif[i] == 0 && verif2[i] == 0)
		{
			//cout << "x" << endl;
			functie(i);
		}
	}

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

	for (unsigned int i = 2 * nrNoduri; i > 0 && complet < nrNoduri; --i)
	{
		b = parcurgere[i];

		if (verif[b] == 0 && b > 0)
		{
			verif[b] = 1;
			fout << b << " ";
			complet++;
		}
	}


}