Cod sursa(job #931422)

Utilizator DEYDEY2Tudorica Andrei DEYDEY2 Data 28 martie 2013 11:00:46
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <set>
#include <deque>
using namespace std;
ifstream fi("sortaret.in");
ofstream fo("sortaret.out");
int N,M;
int i,v1,v2,v,vf;
set <int> P[50001];
set <int> S[50001];
set <int> :: iterator it;
deque <int> L;
deque <int> REZ;
deque <int> :: iterator itr;
int main()
{
    fi>>N>>M;
    for (i=1;i<=M;i++)
    {
        fi>>v1>>v2;
        S[v1].insert(v2);
        P[v2].insert(v1);
    }
    for (i=1;i<=N;i++)
        if (P[i].size()==0)
            L.push_back(i);
    while (REZ.size()!=N)
    {
        if (L.size()==0)
        {
            fo<<-1<<"\n";
            fi.close();
            fo.close();
            return 0;
        }
        v=L.front();
        L.pop_front();
        REZ.push_back(v);
        for (it=S[v].begin();it!=S[v].end();it++)
        {
            vf=(*it);
            P[vf].erase(v);
            if (P[vf].size()==0)
                L.push_back(vf);
        }
    }
    for (itr=REZ.begin();itr!=REZ.end();itr++)
        fo<<(*itr)<<" ";
    fi.close();
    fo.close();
    return 0;
}