Cod sursa(job #1348432)

Utilizator cristian.enciuCristian Enciu cristian.enciu Data 19 februarie 2015 18:17:19
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<stdio.h>
#include<queue>
#include<vector>
#include<set>

using namespace std;

struct node {
	int life;
	vector<int> nexts;
};

node what[50010];
set<int> values;
queue<int> q;

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

	int n, m;

	scanf("%d%d", &n, &m);

	for(int i = 0 ; i < 50010 ; ++i) {
		what[i].life = 0; 
	}

	for(int i = 0 ; i < m ; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);

		if(what[x].life == 0) {
			values.insert(x);
		}

		values.erase(y);
		++what[y].life;
		what[x].nexts.push_back(y);
	}

	for(int i : values) {
		q.push(i);
	}

	while(!q.empty()) {
		int x = q.front();
		q.pop();
		if(what[x].life <= 0) {
			if(what[x].life == 0) {
				printf("%d ", x);
			}

			for(int i  : what[x].nexts) {
				if(what[i].life > 0) {
					--what[i].life;
					q.push(i);
				}
			}
			
			--what[x].life;
		}
	}

	return 0;
}