Cod sursa(job #2197351)

Utilizator killerdonuts358nicolae tudor killerdonuts358 Data 21 aprilie 2018 21:05:49
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
// sortaretopologica.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#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;
}