Cod sursa(job #394542)

Utilizator ErgoVicol Sergiu Constantin Ergo Data 11 februarie 2010 08:47:55
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <vector>

#define NMAX 50100
#define pb push_back

using namespace std;

vector<int> A[NMAX];
int N, M, Sorted[NMAX], nSort, Viz[NMAX];

void Citire(void)
{
	ifstream fin("sortaret.in");
	
	int i, x, y;
	
	fin >>N >>M;
	
	for (i = 1; i <= M; i++)
	{
		fin >>x >>y;
		A[x].pb(y);
	}
	
	fin.close();
}

void DFS(int i)
{
	for (int j = 0; j < A[i].size(); j++)
		if (!Viz[A[i][j]])
		{
			int x = A[i][j];
			DFS(x);
			Sorted[++nSort] = x;
			Viz[x] = 1;
		}
}

void Rezolva(void)
{
	int i;
	
	for (i = 1; i <= N; i++)
		if (!Viz[i])
		{
			DFS(i);
			Sorted[++nSort] = i;
			Viz[i] = 1;
		}
}

void Afiseaza(void)
{
	ofstream fout("sortaret.out");
	
	for (int i = N; i >= 1; i--)
		fout <<Sorted[i] <<' ';
	
	fout.close();
}

int main()
{
	Citire();
	
	Rezolva();
	
	Afiseaza();
	
	return 0;
}