Cod sursa(job #811388)

Utilizator bixcabc abc bixc Data 12 noiembrie 2012 00:55:19
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

#define NMAX 50010

int N, M;
int out_degree[NMAX];
vector <int> graph[NMAX];

void read_data () {

	cin >> N >> M;
	int x, y;
	for (int i = 0; i < M; i++) {
		cin >> x >> y;
		graph[y].push_back (x);
		out_degree[x]++;
	}
}

void sortaret () {
		
	queue <int> Q;
	vector <int> sol;
	for (int i = 1; i <= N; i++)
		if (out_degree[i] == 0)
			Q.push (i);
	
	int node;		
	for (; !Q.empty (); Q.pop ()) {
		node = Q.front ();
		sol.push_back (node);
		for (vector <int>::iterator it = graph[node].begin (); it != graph[node].end (); it++) {
			out_degree[*it]--;
			if (out_degree[*it] == 0)
				Q.push (*it);
		}
	}
	
	for (int i = sol.size () - 1; i >= 0; i--)
		cout << sol[i] << ' ';
}

int main () {
	
	freopen ("sortaret.in", "r", stdin);
	freopen ("sortaret.out", "w", stdout);
	
	read_data ();
	sortaret ();
	
	return 0;
}