Cod sursa(job #755287)

Utilizator milijrCristian Militaru milijr Data 5 iunie 2012 10:43:06
Problema Sortare topologica Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <stdio.h>
#include <vector>
#include <bitset>
using namespace std;

FILE *in, *out;
#define MAXN 50005
vector<int> subord[MAXN];
bitset<MAXN> viz;
int n, m;

struct element_lista
{
	int inf;
	element_lista *urm;
};

element_lista *sortat;

void adauga_coada(element_lista *&prim, element_lista *&ultim, int inf)
{
	element_lista *p = new element_lista;
	p->inf = inf;
	p->urm = NULL;
	if(ultim != NULL)
		ultim->urm = p;
	ultim = p;
	if(prim == NULL)
		prim = ultim;
}

void afis(element_lista *vf)
{
	while(vf != NULL)
	{
		fprintf(out, "%i ", vf->inf);
		vf = vf->urm;
	}
	fprintf(out, "\n");
}

element_lista *prim, *ultim;
void dfs(int nod)
{
	adauga_coada(prim, ultim, nod);
	viz[nod] = 1;
	vector<int>::iterator it;
	for(it = subord[nod].begin(); it != subord[nod].end(); it++)
		if(viz[*it] == 0)
			dfs(*it);
}

void adauga_fii(int nod)
{
	prim = ultim = NULL;
	dfs(nod);
	ultim->urm = sortat;
	sortat = prim;
}

int main()
{
	in = fopen("sortaret.in","r");
	out = fopen("sortaret.out","w");
	fscanf(in, "%i %i", &n, &m);
	int i, nod1, nod2;
	for(i = 1; i <= m; i++)
	{
		fscanf(in, "%i %i", &nod1, &nod2);
		subord[nod1].push_back(nod2); 
	}
	for(i = 1; i <= n; i++)
	{
		if(viz[i] == 0)
		{
			adauga_fii(i);
		}
	}
	afis(sortat);
}