Cod sursa(job #1334857)

Utilizator o_micBianca Costin o_mic Data 4 februarie 2015 18:54:15
Problema Sortare topologica Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>
#define DN 100000

using namespace std;

vector <int> v[DN];
queue <int> q;
int deg[DN], c;

int main(){
	int n, m, a, b;
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);
	//freopen("input.txt", "r", stdin);
	cin >> n >> m;
	for(int i = 0; i < m; ++i){
		cin >> a >> b;
		v[a].push_back(b);
		deg[b] ++;
	}

	for(int i = 1; i < n; ++i)
		if(deg[i] == 0)
			q.push(i);
		
	while(!q.empty()){
		c = q.front();
		q.pop();
		cout << c << " ";
		for(int i = 0; i < v[c].size(); ++i){
			deg[v[c][i]]--;
			if(deg[v[c][i]] == 0)
				q.push(v[c][i]);
		}
	}
	return 0;
}