Cod sursa(job #375149)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 19 decembrie 2009 17:38:00
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
//sortare topologica v2

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

using namespace std;

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

int GI[NM],GE[NM],MU[MM],A[NM],B[NM],N,M;

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

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);
      
      ++GE[a];
      ++GI[b];
    }
    
    int unde=0;
    
    FOR(i,1,N)
    {
      A[i]=unde+1;
      B[i]=unde;
      unde+=GE[i];
    }
    
    freopen("sortaret.in","r",stdin);
    
    scanf("%d %d",&N,&M);
    
    FOR(i,1,M)
    {
      scanf("%d %d",&a,&b);
      MU[++B[a]]=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);
      
      FOR(i,A[nod],B[nod])
      {
        int nnod=MU[i];
        it=H.find(MKP(GI[nnod],nnod));
        H.erase(it);
        --GI[nnod];
        H.insert(MKP(GI[nnod],nnod));
      }
    }
        
    return 0;
}