Cod sursa(job #1091110)

Utilizator horatiu13Horatiu horatiu13 Data 23 ianuarie 2014 19:55:30
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <cstdio>
#define Nmax 50001
#define Mmax 100001
using namespace std;

struct nod
{
	int x;
	nod *urm;
}*G[Nmax];

FILE *fi = fopen("sortare.in", "r");
FILE *fo = fopen("sortare.out", "w");
int gr[Nmax];
int L[Nmax];
int S[Nmax];
int m;
int n;
int si;
int sf;
int ln;

void adauga(int x, int y)
{
	nod *p = new nod;
	p->x = y;
	p->urm = 0;
	
	if (!G[x]) G[x] = p;
	else if (y < G[x]->x)
	{
		p->urm = G[x];
		G[x] = p;
	}
	else
	{
		nod *q;
		nod *r;
		for (q = G[x]; q && y > q->x; r = q, q = q->urm);
		
		r->urm = p;
		if (q) p->urm = q;
	}
}

void citire()
{
	fscanf(fi, "%d%d", &n, &m);
	int x, y;
	
	for (int i = 1; i <= m; i++)
	{
		fscanf(fi, "%d%d", &x, &y);
		gr[y]++;
		adauga(x, y);
	}
}

void sortare()
{
	si = 1;
	sf = 0;
	for (int i = 1; i <= n; i++)
		if (!gr[i])
			S[++sf] = i;
	
	while (si <= sf)
	{
		L[++ln] = S[si];
		int x = S[si++];
		for (nod *p = G[x]; p; p = p->urm)
		{
			gr[p->x]--;
			if (!gr[p->x])
				S[++sf] = p->x;
		}
	}
}

int main()
{
	citire();
	sortare();
	for (int i = 1; i <= n; i++)
		fprintf(fo, "%d ", L[i]);
	
	return 0;
}