Cod sursa(job #2224782)

Utilizator TrixerAdrian Dinu Trixer Data 25 iulie 2018 02:31:13
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <fstream>
#include <list>
#include <vector>

using namespace std;

#define NO_MARK		0
#define TEMP_MARK	1
#define PERM_MARK	2

int n, m;
list<int> topsort;
vector<int> marks;
vector<list<int>> adj_list;

void visit(int x)
{
	if (marks[x] != NO_MARK)
		return;
	
	marks[x] = TEMP_MARK;
	for (auto y : adj_list[x])
		visit(y);

	marks[x] = PERM_MARK;
	topsort.push_front(x);
}

int main(void)
{
	// read input
	ifstream fin;
	fin.open("sortaret.in");
	
	fin >> n >> m;
	marks = vector<int>(n + 1, NO_MARK);
	adj_list = vector<list<int>>(n + 1, list<int>());
	
	for (int i = 0; i < m; i++) {
		int x, y;
		fin >> x >> y;
		adj_list[x].push_back(y);
	}

	fin.close();
	
	// solve
	for (int i = 1; i <= n; i++)
 		if (marks[i] == NO_MARK)
			visit(i);		
	
	// print output
	ofstream fout;
	fout.open("sortaret.out");

	for (auto x : topsort)
		fout << x << ' ';
	fout.close();

	return 0;
}