Cod sursa(job #508482)

Utilizator radubbRadu B radubb Data 8 decembrie 2010 17:02:04
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 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]++;
	}
}


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

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=0;
			
		}
}

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