Cod sursa(job #1706302)

Utilizator srefan1Oncioiu Stefan srefan1 Data 22 mai 2016 10:59:51
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>

using namespace std;

vector<int> g[100001];
int visit[100001];
stack<int> q;

void dfs(int ind)
{
	visit[ind] = 1;
	for (unsigned int i = 0; i < g[ind].size(); i++)
	{
		int ind_fiu = g[ind][i];
		if (visit[ind_fiu] == 0)
		{
			visit[ind_fiu] = 1;
			dfs(ind_fiu);
		}
	}
	q.push(ind);
}

/* Aplica dfs pana se viziteaza toate nodurlie */
void sortare_top(int n)
{
	for (int i = 1; i <= n; i++)
	if (visit[i] == 0)
	{
		dfs(i);
	}
}

int main()
{
	int n, m;
	fstream f, out;
	f.open("sortaret.in", ios::in);
	out.open("sortaret.out", ios::out);

	f >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int x, y;
		f >> x >> y;

		g[x].push_back(y);
	}

	sortare_top(n);

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