Cod sursa(job #359712)

Utilizator cristiprgPrigoana Cristian cristiprg Data 28 octombrie 2009 09:52:41
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <cstdio>
#include <queue>
#include <vector>
#include <list>
using namespace std;
#define DIM 50005
#define pb push_back

int n, m, edges[DIM];
vector<int> a[DIM], q;


void solve()
{
	int i, nod, j; 
	q.pb(0);
	for (i = 1; i <= n; ++i)
		if (edges[i] == 0)
			q.pb(i);
	
	for (i = 1; i <= n; ++i)
	{
		nod = q[i];
		for (j = 1; j <= a[nod][0]; ++j)
		{
			edges [ a[nod][j] ] --;
			if ( edges [ a[nod][j] ] == 0 )
				q.pb( a[nod][j] );
		}
	}
	
	FILE *f = fopen("sortaret.out", "w");
	for (i = 1; i <= n; ++i)
		fprintf(f, "%d ", q[i]);
	
	
}
int main()
{
	int i, x, y;
	FILE *f = fopen("sortaret.in", "r");
	fscanf(f, "%d%d", &n, &m);
	
	for (i = 1; i <= n; ++i)
		a[i].pb(0);
	
	
	for (i = 1; i <= m; ++i)
	{
		fscanf(f, "%d%d", &x, &y);
		a[x][0]++;
		a[x].pb(y);
		edges[y]++;
	}
	fclose(f);
/*	
	for (i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= a[i][0]; ++j)
			printf("%d ", a[i][j]);
		printf("\n");
	}
	*/
	solve();
	
	return 0;
}