Cod sursa(job #199520)

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

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

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);
          
    }
    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());      
    if (GG[nod.second] != nod.first) continue;
    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], tipa);
          G.insert(nod2);
        }
    V[nod.second].resize(0);
    }
    
    return 0;
    }
//RomoCoder in Action Again