Cod sursa(job #524929)

Utilizator tudorsTudor Siminic tudors Data 23 ianuarie 2011 17:11:39
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

int n,m,i,j,k,x,v;
int V[50100],D[50100];
vector <int> M[50100];

void citire()
{
	int a,b;
	f>>n>>m;
	for (i=1;i<=m;i++)
	{
		f>>a>>b;
		M[a].push_back(b);
		D[b]++;
	}
}

void rezolva()
{
	for (i=1;i<=n;i++)
		if (D[i]==0)
		{
			v++;
			V[v]=i;
		}
	for (i=1;i<=n;i++)
	{
		x=V[i];
		for (k=0;k<M[x].size();k++)
		{
			D[M[x][k]]--;
			if (D[M[x][k]]==0)
			{
				v++;
				V[v]=M[x][k];
			}
		}
	}
}

void scrie()
{
	for (i=1;i<=n;i++)
		g<<V[i]<<" ";
}

int main()
{
	citire();
	rezolva();
	scrie();
	f.close();
	g.close();
	return 0;
}