Cod sursa(job #523474)

Utilizator C40DMatei Arsenie C40D Data 18 ianuarie 2011 09:46:25
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<fstream>
#include<stdlib.h>
using namespace std;
int *A[50000], N, M, viz[50000], l[20];
void read()
{
	ifstream in("sortaret.in");
	int i, x, y;
	in>>N>>M;
	for (i=1; i<=N; i++)
	{
		A[i]=(int*)malloc(sizeof(int));
		A[i][0]=0;
	}
	for (i=0; i<M; i++)
	{
		in>>x>>y;
		A[x][0]++;
		A[x]=(int *)realloc(A[x], (A[x][0]+1)*sizeof(int));
		A[x][A[x][0]]=y;
	}
//	for (i=1; i<=N; i++)
//	{
//		cout<<i<<": ";
//		for (x=1; x<=A[i][0]; x++)
//			cout<<A[i][x]<<" ";
//		cout<<endl;
//	}
}
void sTop()
{
	ofstream out("sortaret.out");
	int i, j, k, q, z;
	for (i=1; i<=N; i++)
		viz[i]=0;
	k=0;
	while(k<N)
	{
		for (i=1; i<=N; i++)
			if (A[i][0]==0 && viz[i]==0)
			{
				k++;
//				l[k]=i;
				out<<i<<" ";
				viz[i]=1;
				for (j=1; j<=N; j++)
				{
					q=1;
					while(q<A[j][0] && A[j][q]!=i)
					{
						q++;
					}
					if (q<=A[j][0])
					{
						for (z=q; z<=A[j][0]-1; z++)
						{
							A[j][z]++;
						}
						A[j][0]--;
					}
				}
			}
	}
}
int main()
{
	read();
	sTop();
	return 0;
}