Cod sursa(job #1871742)

Utilizator Rocamadour1497Alexandru Martiniuc Rocamadour1497 Data 7 februarie 2017 17:11:37
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <fstream>
#include <vector>



using namespace std;

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

const int max = 50005;

int n, m;
vector<int> g[max];
int degr[max];
int q[max];

void soto()
{
	int i, j;
	int x;

	for (i = 1; i <= n; i++)
	{
		if (degr[i] == 0) q[++q[0]] = i;
	}
	for (i = 1; i <= n; i++)
	{
		x = q[i];
		for (vector<int>::iterator it = g[x].begin(); it != g[x].end(); it++)
		{
			degr[*it]--;
			if (degr[*it] == 0) q[++q[0]] = *it;

		}
	}
}

int main()
{
	fin >> n >> m;
	int x, y, i, j;
	for (i = 1; i <= m; i++)
	{
		fin >> x >> y;
		g[x].push_back(y);
		degr[y]++;
	}

	soto();

	for (i = 1; i <= n; i++)
		gout << q[i] << " ";
}