Cod sursa(job #2671957)

Utilizator killerdonuttudor nicolae killerdonut Data 12 noiembrie 2020 21:24:38
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
 
using namespace std;
 
ifstream in("sortaret.in");
ofstream out("sortaret.out");
 
int n, m;
 
vector <int> *v;
stack <int>sol;
bool *vis;
 
void DFS(int i)
{
	vis[i] = true;
	for(int j = 0; j < v[i].size(); j++)
	{
		if(vis[v[i][j]] == false)
			DFS(v[i][j]);
	}
	sol.push(i);
}
 
int main()
{
	in >> n >> m;
	v = new vector <int>[n+1];
	vis = new bool[n + 1];
 
	for (int i = 1; i <= n; i++)
		vis[i] = false;
 
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		in >> x >> y;
		v[x].push_back(y);
	}
 
	for (int i = 1; i <= n; i++)
	{
		if (vis[i] == false)
			DFS(i);
	}
 
	while (!sol.empty())
	{
		out << sol.top() << ' ';
		sol.pop();
	}
 
	delete[] v, vis;
    return 0;
}