Cod sursa(job #1091120)

Utilizator horatiu13Horatiu horatiu13 Data 23 ianuarie 2014 22:02:20
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 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 L[Nmax];
char viz[Nmax];
int m;
int n;
int ln;

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

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

// 1 - marcat temporar
// 2 - marcat permanent
void viziteaza(int x)
{
	if (viz[x] == 1)
		printf("GRAFUL CONTINE CEL PUTIN UN CICLU");
	if (!viz[x])
	{
		viz[x] = 1;
		for (nod *p = G[x]; p; p=p->urm)
			viziteaza(p->x);
		viz[x] = 2;
		L[++ln] = x;
	}
}

int main()
{
	citire();
	for (int i = 1; i <= n; i++)
		if (!viz[i])
			viziteaza(i);
	for (; ln; ln--)
		fprintf(fo, "%d ", L[ln]);
	return 0;
}