Cod sursa(job #1529267)

Utilizator redcrocodileIlies Andreea redcrocodile Data 20 noiembrie 2015 17:52:39
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <set>
#include <queue>
#include <vector>

using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
set<int> S,S1;
queue<int> Q;
vector<int> V[50001],V1[50001];
std::set<int>::iterator it;
std::vector<int>::iterator itt,ittt;
int x,i,n,m,a,b,y;

int main()
{
    f>>n>>m;
    for (i=1;i<=m;i++)
{
    f>>a>>b;
    V[a].push_back(b);
    V1[b].push_back(a);
}
   for (i=1;i<=n;i++)
    if (V1[i].empty()) S.insert(i);
   while (!S.empty())
    {
        it = S.begin();
        x = *it;
        S.erase(it);
        Q.push(x);
        for (itt = V[x].begin(); itt!=V[x].end(); itt++)
        {
            y = *itt;
            for (ittt = V1[y].begin(); ittt!=V[y].end(); ittt++)
            if (*ittt==x) {V1[y].erase(ittt); break;}
            if (V1[y].empty()) S.insert(y);
        }
    }
    while(!Q.empty())
    {
        g<<Q.front()<<" ";
        Q.pop();
    }

    return 0;
}