Cod sursa(job #375144)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 19 decembrie 2009 17:20:05
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
//sortare topologica v1

#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<algorithm>

using namespace std;

#define NM 50005
#define PB push_back
#define MKP make_pair
#define FOR(i,a,b)for(int i=(a);i<=(b);++i)

vector<int> G[NM];

set<pair<int,int> > H;
set<pair<int,int> >::iterator it;

int GI[NM],N,M;

int main()
{
    int a,b;
    
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    
    scanf("%d %d",&N,&M);
    
    FOR(i,1,M)
    {
      scanf("%d %d",&a,&b);
      G[a].PB(b);
      ++GI[b];
    }
    
    FOR(i,1,N)
      H.insert(MKP(GI[i],i));
      
    while(!H.empty())
    {
      it=H.begin();
      int nod=it->second;
      H.erase(it);
      printf("%d ",nod);
      
      int sz=G[nod].size();
      FOR(i,0,sz-1)
      {
        int nnod=G[nod][i];
        it=H.find(MKP(GI[nnod],nnod));
        H.erase(it);
        --GI[nnod];
        H.insert(MKP(GI[nnod],nnod));
      }
    }  
    
    return 0;
}