Cod sursa(job #749098)

Utilizator krityxAdrian Buzea krityx Data 15 mai 2012 19:30:52
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <set>

using namespace std;


int main()
{
    ifstream f("sortaret.in");
    ofstream g("sortaret.out");
    vector<int> G[50001],L;
    set<int> S;
    set<int>::iterator sit;
    int N,M,a,b,i,x,grad[50001];
    f>>N>>M;
    for(i=1;i<=N;i++)
    {
        grad[i]=0;
        S.insert(i);
    }
    for(i=1;i<=M;i++)
    {
        f>>a>>b;
        G[a].push_back(b);
        grad[b]++;
        S.erase(b);
    }
    while(!S.empty())
    {
        sit=S.begin();
        x=*sit;
        S.erase(x);
        L.push_back(x);
        for(vector<int>::iterator it=G[x].begin();it!=G[x].end();it++)
        {
            if(grad[*it])
            {
               grad[*it]--;
               if(grad[*it]==0) S.insert(*it);
            }
            //G[x].erase(it);

        }
    }

    for(vector<int>::iterator it=L.begin();it!=L.end();it++)
    {
        g<<*it<<" ";
    }

    f.close();
    g.close();
    return 0;
}