Cod sursa(job #2197349)

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

//#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int n, m;

vector <int> *v,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_back(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);
	}

	for (int i = n - 1; i >= 0; i--)
	{
		out << sol[i] << ' ';
	}

	delete[] v, vis;
    return 0;
}