Cod sursa(job #2692583)

Utilizator bubblegumixUdrea Robert bubblegumix Data 3 ianuarie 2021 11:41:33
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include<fstream>
#include<list>
#include<cstring>
#include<string.h>
#include<stack>
using namespace std;
ifstream cin("sortare.in");
ofstream cout("sortare.out");

class graph
{
private:
	int n;
	list<int>* adj;
	void DFS(int n, bool* viz,stack<int> &s);
public:
	graph(int n);
	void addEdge(int x, int y);
	void printsorted();
	~graph();
};

graph::graph(int n)
{
	this->n = n;
	adj = new list<int>[n+1];
}
graph::~graph()
{
	delete[] adj;
}
void graph::addEdge(int x, int y)
{
	adj[x].push_back(y);
}
void graph::DFS(int n, bool* viz, stack<int>& s)
{
	viz[n] = true;
	for (auto it : adj[n])
		DFS(it, viz, s);
	s.push(n);
}
void graph::printsorted()
{
	stack<int> s;
	bool* viz = new bool[n + 1];
	memset(viz, false, n + 1);
	for (int i = 1; i <= n; i++)
		if (!viz[i])
			DFS(i, viz, s);
	while (!s.empty())
	{
		cout << s.top()<<" ";
		s.pop();
	}
}


int main()
{
	int n, m, x, y;
	cin >> n >> m;
	graph G(n);
	for (int i = 1; i <= m; i++)
	{
		cin >> x >> y;
		G.addEdge(x, y);
	}
	G.printsorted();

	cin.close();
	cout.close();
	return 0;
}