Cod sursa(job #1221505)

Utilizator paulhermanPaul Herman paulherman Data 20 august 2014 16:03:34
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

const int MAX_V = 50005;
int V, E, deg[MAX_V];
vector<int> adj[MAX_V], order;
queue<int> q;

int main() {
    freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);
	
	scanf("%d %d", &V, &E);
	for (int i = 0; i < E; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		adj[u].push_back(v);
		deg[v]++;
	}
	
	for (int i = 1; i <= V; i++)
		if (deg[i] == 0)
			q.push(i);
			
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		order.push_back(u);
        printf("%d\n", u);
		
		for (int i = 0; i < (int)adj[u].size(); i++) {
			int v = adj[u][i];
			deg[v]--;
			if (deg[v] == 0)
				q.push(v);
		}
	}
	
	for (int i = 0; i < (int)order.size(); i++)
		printf("%d ", order[i]);
	
	return 0;
}