Cod sursa(job #622988)

Utilizator wamfeverDobos Ionut wamfever Data 18 octombrie 2011 20:24:17
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<fstream>
#include<iostream>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int d[100001], q[100001];
int n, m, i;

struct lista{
				int nod;
				lista *urm;
			} *G[100001];
			
void adauga(int i, int j)
{
	lista *p = G[i];
	while(p && p->nod-j) p = p->urm;
	if(!p)
	{
		++d[j];
		p = new lista;
		p->nod = j;
		p->urm = G[i];
		G[i] = p;
	}
	//fclose(stdin);
}

void citeste()
{
	//freopen("sortaret.in", "r", stdin);
	//scanf("%d %d", &n, &m);
	int i, j;
	f >> n >> m;
	while(m--) /*scanf("%d %d", &i, &j)*/ f >> i >> j, adauga(i, j);
}

int main()
{
	citeste();
	int a=1, k=0;
	lista *p;
	for(i=1; i<=n; i++) {/*cout << d[i] << " "; */if(!d[i]) q[++k] = i; }
	while(a <= k)
	{
		p = G[ q[a] ];
		while(p)
		{
			d[ p->nod ] --;
			if( !d[ p->nod ] ) q[++k] = p->nod;
			p = p->urm;
		}
		
		a++;
	}
	//freopen("sortaret.out", "w", stdout);
	for(i=1; i<=n; i++) g << q[i] << " ";//printf("%d ", d[i]);
	//printf("\n");
	g << "\n";
	//fclose(stdout);
	return 0;
}