Cod sursa(job #1214492)

Utilizator andreas.chelsauAndreas Chelsau andreas.chelsau Data 30 iulie 2014 16:20:06
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;

vector<int> l[50000 + 5];
void add(int i, int j){
	l[i].push_back(j);
}
int s[50000 + 5];
vector<int> sortedElements;
void dfs(int i){
	s[i] = 1;
	vector<int> n = l[i];
	for(int j = 0; j < n.size(); j++){
		if(s[n[j]] == 0){
			s[n[j]] = 1;
			dfs(n[j]);
		}
	}
	sortedElements.push_back(i);
}
void top_sort(int n){
	for(int i = 1; i <= n; i++){
		if(!s[i])
			dfs(i);
	}
	for(int i = sortedElements.size() - 1; i >= 0; i--)
		printf("%d ",sortedElements[i]);
}
int main(){
	int n,m;
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	scanf("%d%d",&n,&m);
	while(m--){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
	}
	top_sort(n);
	return 0;
}