Cod sursa(job #1705509)

Utilizator alex95panPandelea Alexandru alex95pan Data 20 mai 2016 18:27:46
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 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 solve(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);
	}

    solve(n);

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