Cod sursa(job #2905979)

Utilizator ispir_andreiIspir andrei ispir_andrei Data 24 mai 2022 18:18:09
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <stack>

using namespace std; 

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

/*const int N = 50000;
vector<int> a[N + 1];
int nrp[N+1];

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

	for (int i = 0; i < m; i++)
	{
		int x, y;
		in >> x >> y;
		a[x].push_back(y);
		nrp[y]++;
	}
	queue<int> q;
	
	for (int i = 1; i <= n; i++)
	{
		if (nrp[i] == 0)
		{
			q.push(i);
		}
	}

	while (!q.empty())
	{
		int x = q.front();
		out << x << " ";
		q.pop();

		for (auto y : a[x])
		{
			nrp[y]--;
			if (nrp[y] == 0)
			{
				q.push(y);
			}
		}
	}

	in.close();
	out.close();
	
	return 0;
}
*/
//DFS::

const int N = 50000;
stack<int> stiva;
bool viz[N+1];
vector<int> a[N + 1];

void dfs(int x)
{
	viz[x] = true;

	for (auto y : a[x])
	{
		if (!viz[y])
		{
			dfs(y);
		}
	}
	stiva.push(x);
	
}

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

	for (int i = 0; i < m; i++)
	{
		int x, y;
		in >> x >> y;
		a[x].push_back(y);
	}

	for (int i = 1; i <= n; i++)
	{
		if (!viz[i])
		{
			dfs(i);
		}
	}

	while (!stiva.empty())
	{
		out << stiva.top() << " ";
		stiva.pop();
	}

	in.close();
	out.close();

	return 0;
}