Cod sursa(job #1244893)

Utilizator roxana.istratePoenaru Roxana roxana.istrate Data 18 octombrie 2014 13:02:53
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <stack>
#include <vector>

#define MAX  50001

using namespace std;

vector<vector<int>> adj(MAX);
int N, M;
vector<int> cnt(MAX, 0);

int main(){
	freopen("topologica.in", "r", stdin);
	freopen("topologica.out", "w", stdout);
	stack<int> q;
	int from, to;
	scanf("%d%d", &N, &M);
	for(int i = 0; i < M; i++){
		scanf("%d%d", &from, &to);
		adj[--from].push_back(--to);
		cnt[to]++;
	}
	
	for(int i = 0; i < N; i++){
		if(cnt[i] == 0){
			q.push(i);
		}
	}
	
	while(!q.empty()){
		int node = q.top();
		q.pop();
		printf("%d ", node+1);
		for(int i = 0; i < adj[node].size(); i++){
			cnt[adj[node][i]]--;
			if(cnt[adj[node][i]] == 0){
				q.push(adj[node][i]);
			}
		}
	}
	return 0;
}