Cod sursa(job #1477416)

Utilizator alexandru.huleaAlexandru Hulea alexandru.hulea Data 26 august 2015 11:06:13
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {

	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);

	int n, m;
	scanf("%i", &n);
	scanf("%i", &m);

	vector<int>* vecini = new vector<int> [n];
	int* grad_interior = new int[n];
	bool* visited = new bool[n];
	int nr_visited = 0;
	for (int i = 0; i < n; i++) {
		grad_interior[i] = 0;
		visited[i] = false;
	}

	for (int i = 0; i < m; i++) {
		int x, y;
		scanf("%i", &x);
		scanf("%i", &y);
		x--;
		y--;
		vecini[x].push_back(y);
		grad_interior[y]++;
	}

	queue<int> q;
	vector<int> final_list;


	for (int i = 0; i < n; i++) {
		if (grad_interior[i] == 0) {
			q.push(i);
			final_list.push_back(i);
			visited[i] = true;
			nr_visited++;
			for (int j = 0; j < vecini[i].size(); j++) {
				grad_interior[ vecini[i][j] ]--;
			}
		}
	}

	while(nr_visited < n) {
		for (int i = 0; i < n; i++) {
			if (!visited[i] && grad_interior[i] == 0) {
				q.push(i);
				final_list.push_back(i);
				visited[i] = true;
				nr_visited++;
				for (int j = 0; j < vecini[i].size(); j++) {
					grad_interior[ vecini[i][j] ]--;
				}
			}
		}
	}

	for (int i = 0; i < n; i++) {
		printf("%i ", final_list[i] + 1);
	}

	fclose(stdin);
	fclose(stdout);
	return 0;
}