Cod sursa(job #199517)

Utilizator romocoderRomo Coder romocoder Data 19 iulie 2008 08:18:38
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
//@RomoCoder
#include <map>
#include <set>
#include <algorithm>
#include <vector>
#include <cstdio>

using namespace std;
set<pair<int, int> > G; //<grad, nod>
int GG[60001];

vector<vector<int> > V;
int main() {
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    int N, M;
    scanf("%d %d", &N, &M);
    V.resize(N+3);

    while (M--)
    {
          int a, b;
          scanf("%d %d", &a, &b);
          ++GG[b]; //gradu creste
          
          V[a].push_back(b);
          
//          pair<int, int> nod(GG[b]-1, b);
  //        if (G.find(nod) != G.end()) 
    //      {
      //        G.erase(G.find(nod));
        //  }
          //nod.first = GG[b];
          //G.insert(nod);
    }
    for ( int i = 1; i <= N; ++i) G.insert(make_pair(GG[i], i));
    
    while (!G.empty())
    {
    pair<int, int> nod;
    nod = *G.begin();
    //erase it
    G.erase(G.begin());      
    printf("%d ", nod.second);
    //update it
    for (int i = 0; i < V[nod.second].size(); ++i)     {
        int tipa = V[nod.second][i];
        
        GG[tipa]--;
        
        pair<int, int> nod2(GG[tipa]+1, tipa);
          if (G.find(nod2) != G.end())           {
              G.erase(G.find(nod2));
          }
          nod2.first = GG[tipa];
          G.insert(nod2);
        }
    V[nod.second].resize(0);
    }
    
    return 0;
    }
//RomoCoder in Action Again