Cod sursa(job #1240877)

Utilizator sorin2kSorin Nutu sorin2k Data 12 octombrie 2014 11:34:35
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<iostream>
#include<queue>
#include<vector>
using namespace std;

vector<int> adj[50001];
int in[50001];
int n, m;

int main() {
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);
	int x, y, i, current;
	queue<int> q;
	scanf("%d %d", &n, &m);
	for(i = 0; i < m; i++) {
		scanf("%d %d", &x, &y);
		adj[x].push_back(y);
		in[y]++;
	}
	for(i = 1; i <= n; i++) {
		if(in[i] == 0) {
			q.push(i);
		}
	}
	while(!q.empty()) {
		current = q.front();
		q.pop();
		printf("%d ", current);
		for(vector<int>::iterator it = adj[current].begin(); it != adj[current].end(); ++it) {
			in[*it]--;
			if(in[*it] == 0) {
				q.push(*it);
			}
		}
	}
	return 0;
}