Cod sursa(job #1334839)

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

using namespace std;

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

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

	for(int i = 0; i < vert.size(); ++i)
		if(deg[vert[i]] == 0 && !viz[vert[i]]){
			q.push(vert[i]);
			viz[vert[i]] = 1;
		}
		
	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;
}