Cod sursa(job #1260423)

Utilizator pulseOvidiu Giorgi pulse Data 11 noiembrie 2014 11:53:19
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50005;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

int N, M;
int Grad[MAXN], V[MAXN];
vector <int> G[MAXN];

void Sortare_Topologica()
{
	for (int i = 1; i <= N; ++i)
	{
		if (Grad[i] == 0)
			V[++V[0]] = i;
	}
	for (int i = 1; i <= N; ++i)
	{
		int node = V[i];
		for (vector <int> :: iterator it = G[node].begin(); it != G[node].end(); ++it)
		{
			int v = *it;
			Grad[v]--;
			if (Grad[v] == 0)
				V[++V[0]] = v;
		}
	}
	for (int i = 1; i <= N; ++i)
		fout << V[i] << " ";
}

int main()
{
	fin >> N >> M;
	for (int i = 1, a, b; i <= M; ++i)
	{
		fin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
		++Grad[b];
	}
	Sortare_Topologica();
	fin.close(); fout.close();
	return 0;
}