Cod sursa(job #2632328)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 2 iulie 2020 20:08:15
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <stack>

using namespace std;

ifstream be("sortaret.in");
ofstream ki("sortaret.out");

class graf
{
	int CS;
	vector<list<int> > sz_lista;
public:
	graf(int CS);
	void uj_el(int x, int y);
	void top_rendez();
};

graf::graf(int CS)
{
	this->CS = CS;
	sz_lista.resize(CS+1, list<int>());
}

void graf::uj_el(int x, int y)
{
	sz_lista[x].push_back(y);
}

void graf::top_rendez()
{
	stack<int> verem;
	vector<bool> latogatott(CS + 1, false);
	stack<int> eredmeny;

	for (int kezdo = 1; kezdo <= CS; kezdo++)
	{
		if (latogatott[kezdo] == false)
		{
			verem.push(kezdo);
			latogatott[kezdo] = true;
			while (!verem.empty())
			{
				int akt = verem.top();
				if (sz_lista[akt].size() > 0)
				{
					int sz = sz_lista[akt].front();
					sz_lista[akt].pop_front();
					if (!latogatott[sz])
					{
						latogatott[sz] = true;
						verem.push(sz);
					}
					             
				  
				}
				else 
				{
					verem.pop();
					eredmeny.push(akt);
				}
			}
		}
	}

	while (!eredmeny.empty())
	{
		ki << eredmeny.top()<<" ";
		eredmeny.pop();
	}

}

void beolvas(graf& g, int n, int m)
{
	for (int i = 0; i < m; i++)
	{
		int x, y;
		be >> x >> y;
		g.uj_el(x,y);
	}
}


int main()
{
	int n, m;
	be >> n >> m;

	graf g(n);

	beolvas(g, n, m);

	g.top_rendez();

	return 0;
}