Cod sursa(job #2457759)

Utilizator stefzahZaharia Stefan Tudor stefzah Data 18 septembrie 2019 17:47:41
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
// Havel Hakimi.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
#include <vector>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int gi[50005],ge[50005],n,m,sol[50005];
queue <int>p;
vector <int> v[50005];
bool viz[50005];
void DFS(int nod)
{
	viz[nod] = 1; //cout << nod << "\n";
	for (int i = 0; i < v[nod].size(); i++)
		if (viz[v[nod][i]] == 0) {
								  DFS(v[nod][i]); 
								 }
	//cout << nod << "\n";
	p.push(nod);
}
int main()
{
	int x, y, ct=0;
	fin >> n >> m;
	for(int i=0;i<m;i++)
	{
		fin >> x >> y;
		v[x].push_back(y);
		ge[x]++;
		gi[y]++;
	}

	for (int i = 1; i <= n; i++)
	{
		if (gi[i]==0)DFS(i);
		//cout << "\n";
	}
	ct = n;
	while (!p.empty())
	{
		sol[ct] = p.front();
		p.pop();
		ct--;
	}
	for (int i = 1; i <= n; i++)
		fout << sol[i]<<" ";

}