Cod sursa(job #1068639)

Utilizator andy1496Casu-Pop Andrei andy1496 Data 28 decembrie 2013 15:57:57
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

typedef struct { int x; int y; } per;

int main(){
	int n, m, s, i, j, nv;
	vector<per> edges;
	vector<int> *v;
	queue<int> que;

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

	scanf("%d %d", &n, &m);
	
	vector<int> ch(n+1, 0);

	v = new vector<int>[n+1];

	edges.reserve(m+2);

	per p;
	for (i = 0; i <= m-1; i++){
		scanf("%d %d", &p.x, &p.y);
		edges.push_back(p);
		ch[p.y]++;
	}

	for (i = 0; i <= n-1; i++){
		v[i].reserve(ch[i]);
	}

	for (i = 0; i <= m-1; i++){
		p = edges[i];
		v[p.x].push_back(p.y);
	}

	for (i = 1; i <= n; i++) {
		if (ch[i] == 0) {
			que.push(i);
			printf("%d ", i);
		}
	}

	while (!que.empty()){
		p.x = que.front();
		que.pop();
		for (i = 0; i < v[p.x].size(); i++){
			nv = v[p.x][i];
			ch[nv]--;
			if (ch[nv] == 0){
				que.push(nv);
				printf("%d ", nv);
			}
		}
	}
	
	return 0;
}