Cod sursa(job #508477)

Utilizator radubbRadu B radubb Data 8 decembrie 2010 16:36:52
Problema Sortare topologica Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
// constructing vectors
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

#define nmax 50002
vector <int> nod[nmax];

long n,m,p[nmax],crt,g[nmax],viz[nmax];

void citire()
{
	long i,x,y;
	ifstream in("sortaret.in");
	in>>n>>m;
	for(i=1;i<=m;i++)
	{
		in>>x>>y;
		nod[x].push_back(y);
		g[y]++;
	}
}

void sort_t()
{
	long i,j;
	for(i=1;i<=n;i++)
		if(!g[i] && !viz[i])
		{
			for(j=0;j<nod[i].size();j++)
				g[nod[i][j]]--;
			viz[i]=1;
			p[++crt]=i;
			if(crt==n)
				break;
			else
				i=1;
		}
}

void afisare()
{
	long i;
	ofstream out("sortaret.out");
	for(i=1;i<=n;i++)
		out<<p[i]<<" ";

}

int main ()
{
	citire();
	sort_t();
	afisare();
}