Cod sursa(job #596447)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 17 iunie 2011 13:15:38
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<fstream>
#include<cstdlib>
using namespace std;
int n,m;
int *A[50005],np[50005];
int postordine[50005],nr;
bool vizitat[50005];
//np[i] = numarul predecesorilor sai care nu au fost inca plasati pe niveluri
//adica gradul interior in subgraful curent

void Citire()
{
	int i,x,y;
	ifstream fin("sortaret.in");
	fin>>n>>m;
	for(i=1;i<=n;i++)
	{
		A[i]=(int *)realloc(A[i],sizeof(int));
		A[i][0]=0;
	}
	for(i=1;i<=m;i++)
	{
		fin>>x>>y;
		//construiesc graful
		A[x][0]++;
		A[x]=(int *)realloc(A[x],(A[x][0]+1)*sizeof(int));
		A[x][A[x][0]]=y;
		np[y]++;
	}
	fin.close();
}

void DFS(int x)
{
	int i;
	vizitat[x]=true;
	for(i=1;i<=A[x][0];i++)
	{
		if(vizitat[A[x][i]]==false)
			DFS(A[x][i]);
	}
	postordine[++nr]=x; //numerotez nodurile grafului in postordine
	//nodul x este numerotat dupa ce toti succesorii sai au fost numerotati
}

int main()
{
	int i;
	Citire();
	ofstream fout("sortaret.out");
	//parcurgem graful DFS determinand ordinea nodurilor
	for(i=1;i<=n;i++)
	{
		if(vizitat[i]==false)
			DFS(i);
	}
	for(i=n;i>0;i--)
		fout<<postordine[i]<<' ';
	fout<<"\n";
	fout.close();
	return 0;
}