Cod sursa(job #1722023)

Utilizator M.AndreiMuntea Andrei Marius M.Andrei Data 27 iunie 2016 01:02:51
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#ifndef _CRT_NONSTDC_NO_WARNINGS
#define _CRT_NONSTDC_NO_WARNINGS

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <vector>
#include <string.h>
using namespace std;


vector<int> edges[50002];
vector<int> sorted;
int visited[50002];

void do_sort(int k) {
	visited[k] = 1;
	for (size_t i = 0; i < edges[k].size(); i++) {
		if (!visited[edges[k][i]])do_sort(edges[k][i]);
	}
	sorted.push_back(k);
}

void topSort(const int& vertexNumber) {
	for (int i = 1; i <= vertexNumber; i++) {
		if (!visited[i]) do_sort(i);
	}
}

int main() {

	ifstream fin{ "sortaret.in" };
	ofstream fout{ "sortaret.out" };
	memset(visited, 0, 50002 * sizeof(int));

	int n, m, i, x, y;
	for (i = 0, fin >> n >> m; i < m; i++) {
		fin >> x >> y;
		edges[x].push_back(y);
	}

	topSort(n);
	while (!sorted.empty()) { fout << sorted[sorted.size() - 1]<<" "; sorted.pop_back(); }


	fin.close();
	fout.close();
	return EXIT_SUCCESS;
}

#endif //_CRT_NONSTDC_NO_WARNINGS