Cod sursa(job #944114)

Utilizator sorin2kSorin Nutu sorin2k Data 27 aprilie 2013 14:47:30
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<fstream>
#include<list>
#include<vector>
using namespace std;

int *vizitat;
list<int> l; // lista in care vom adauga in fata elementele care nu mai au descendenti de accesat

void DFS(vector<int> *adj, int start)
{
	int i;
	for(i = 0; i < (int)adj[start].size(); i++)
	{
		if(vizitat[adj[start][i]] == 0)
		{
			vizitat[adj[start][i]] = 1;
			DFS(adj, adj[start][i]);
		}
	}
	l.push_front(start);
}

int main()
{
	ifstream fin("sortaret.in");
	ofstream fout("sortaret.out");
	int n, m, i, u, v;
	vector<int> *adj;
	fin >> n >> m;
	adj = new vector<int>[n];
	vizitat = new int[n];
	for(i = 0; i < n; i++)
		vizitat[i] = 0;
	for(i = 0; i < m; i++)
	{
		fin >> u >> v;
		u--;
		v--; // retinem nodurile de la 0 la n - 1
		adj[u].push_back(v);
	}
	for(i = 0; i < n; i++)
	{
		if(vizitat[i] == 0)
		{
			vizitat[i] = 1;
			DFS(adj, i);
		}
	}
	while(!l.empty())
	{
		fout << l.front() + 1 << " ";
		l.pop_front();
	}
	return 0;
}