Cod sursa(job #1217159)

Utilizator pavlov.ionPavlov Ion pavlov.ion Data 6 august 2014 19:22:24
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<fstream>
#include<vector>
#include<algorithm>
#define MAXN 50005
#define pb push_back
using namespace std;
ifstream cin("sortaret.in");
ofstream cout("sortaret.out");
struct timp{
	   int time;
	   int nod; } T[MAXN];
int N,M,t=0;
char viz[MAXN];
vector<int> G[MAXN];
int cmp(timp a,timp b) {
	return (a.time>b.time); }
void DFS(int x) {
	 int i;
	 for(i=0;i<G[x].size();i++)
	           if(!viz[G[x][i]]) {
			   					 viz[G[x][i]]=1;
								 DFS(G[x][i]); }
	T[x].time=++t;
}
int main() {
	int i,j,x,y;
	cin>>N>>M;
		for(i=1;i<=N;i++)
	              T[i].nod=i;
	for(i=1;i<=M;i++) {
	             cin>>x>>y;
				 G[x].pb(y); }
	for(i=1;i<=N;i++) 
				if(!viz[i]) {
							viz[i]=1;
							DFS(i); }	  
     sort(T+1,T+N+1,cmp);
	 for(i=1;i<=N;i++)
	         cout<<T[i].nod<<" ";
	return 0;
}