Cod sursa(job #790541)

Utilizator mihaiSimuSimu Mihai mihaiSimu Data 21 septembrie 2012 17:48:03
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <stdio.h>
#include <bitset>
#include <vector>
using namespace std;

vector<int> v;
bitset<50006>viz;
//int a[50006][50006];
vector< vector<int> > a;
void df(int nod){
	viz[nod]=1;
	for(int i=0;i<a[nod].size();i++){
		if(!viz[a[nod][i]])
			df(a[nod][i]);
	}
	v.push_back(nod);
}


int main(){
	int n,m,x,y;
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	
	viz.reset();
	scanf("%d",&n);
	scanf("%d",&m);
	for(int i=0;i<=n;i++){
		vector<int> newV;
		a.push_back(newV);
	}

	for(int i=0;i<m;i++){
		scanf("%d",&x);scanf("%d",&y);
		a[x].push_back(y);
	}

	for(int i=1;i<=n;i++)
		if(!viz[i])
			df(i);

	for(int i=v.size()-1;i>=0;i--){
		printf("%d ",v[i]);
	}

	return 0;
}