Cod sursa(job #156159)

Utilizator anoukAnca Dumitrache anouk Data 12 martie 2008 13:15:03
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <cstdio>
#include <queue>
#define DIM 50005
using namespace std;

typedef struct Nod {
	int vf;
	Nod* next;
} NOD, *PNOD;
PNOD L[DIM];
int N, M, grad[DIM];
queue<int> Q;

void Add(int x, int y)
{
	PNOD p = new NOD;
	p->vf = y;
	p->next = L[x];
	L[x] = p;
}

int main()
{
	FILE *fin = fopen("sortaret.in", "r");
	FILE *fout = fopen("sortaret.out", "w");
	
	fscanf(fin, "%d%d", &N, &M);
	int x, y;
	for (int i = 1; i <= M; i++)
	{
		fscanf(fin, "%d%d", &x, &y);
		Add(x, y);
		grad[y]++;
	}
	
	for (int i = 1; i <= N; i++)
		if (!grad[i]) Q.push(i);
	while (!Q.empty())
	{
		int i = Q.front();
		fprintf(fout, "%d ", i);
		for (PNOD p = L[i]; p; p = p->next)
		{
			grad[p->vf]--;
			if (!grad[p->vf]) Q.push(p->vf);
		}
		Q.pop();
	}
	
	fclose(fin);
	fclose(fout);
	return 0;
}