Cod sursa(job #1216508)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 4 august 2014 18:48:26
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
ifstream fi("sortaret.in");
ofstream fo("sortaret.out");

struct info{
       int nivel;
       int nr;
};

const int max_n = 50004;

vector <int> a[max_n];
int i,n,m,x,y,level;
info t[max_n];

bool comp(info x, info y){ return (x.nivel<y.nivel); }

void dfs(int nod){
     level++;
     for(unsigned int j=0;j<a[nod].size();j++)
       if(t[a[nod][j]].nivel<level){ t[a[nod][j]].nivel=level; dfs(a[nod][j]); } 
}
 
int main(){
    fi>>n>>m;
    for(i=1;i<=m;i++){
                      fi>>x>>y;
                      a[x].push_back(y);
                     }
    
    for(i=1;i<=n;i++) t[i].nivel=0,t[i].nr=i;
    
    for(i=1;i<=n;i++)
      if(!t[i].nivel){
                      level=0;
                      dfs(i);
                     }
    
    sort(t+1,t+n+1,comp);
    
    for(i=1;i<=n;i++) fo<<t[i].nr<<" ";
    
    fi.close();
    fo.close();
    return 0;
}