Cod sursa(job #2943705)

Utilizator JaguarKatStere Teodor Ioanin JaguarKat Data 21 noiembrie 2022 15:45:24
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.65 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, m, k;
int grad[50001];
int v[50001];
vector<int> a[50001];


int main()
{
	fin >> n >> m;
	for(int x, y, i = 1; i <= n; ++i)
	{
		fin >> x >> y;
		a[x].push_back(y);
		grad[y]++;
	}
	for(int i = 1; i <= n; ++i)if(grad[i] == 0)v[++k] = i;
	int p = 1, u = k;
 	while(p <= u)
 	{
 		int x = v[p];
 		for(auto i = a[x].begin(); i != a[x].end(); ++i)
 		{
 			--grad[*i];
 			if(grad[*i] == 0)
 			{
 				++u;
 				v[++k] = *i;
 			}
 		}
 		++p;
 	}
 	for(int i = 1; i <= k; ++i)fout << v[i] << ' ';
	return 0;
}