Cod sursa(job #1972010)

Utilizator Y0da1NUME JMECHER Y0da1 Data 21 aprilie 2017 15:06:48
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <bitset>
#include <vector>
#include <algorithm>
#include <list>
using namespace std;
int n, m;

bitset <50006> vizitat;
bitset <50006> arepred;
class nod{
public:
    unsigned int id;
    vector <int> vecini;
};
list <nod> L;
vector <pair<nod, int> > V (50001);
void defeu (int x, int prev)
{

    if (!vizitat[x])
    {
        vizitat[x] = 1;
        V[x].second = V[prev].second + 1;
        for(int i = 0; i< V[x].first.vecini.end() - V[x].first.vecini.begin(); ++i)
            defeu(V[x].first.vecini[i], V[x].first.id);
        L.push_front(V[x].first);
        return;
    }
    else return;
}

bool cmp (pair<nod, int> p1, pair<nod, int> p2)
{
    return p1.second < p2.second;
}
int main()
{
    ifstream in ("sortaret.in");
    ofstream out ("sortaret.out");

    in>>n>>m;

    int i, x, y;

    for(i=0;i<m;++i)
    {
        in>>x>>y;
        V[x].first.vecini.push_back(y);
        arepred[y]=1;
    }
    for(i=1;i<=n;++i)
    {
        V[i].first.id=i;
        //cout<<arepred[i]<<" ";
    }
    for (i = 1; i<=n;++i)
        if(!arepred[i])
            defeu(i, i);
    //sort (V.begin(), V.begin()+n+1, cmp);
    /*for (i = 1; i<=n;++i)
    {
        cout<<"<"<<V[i].first.id<<", "<<V[i].second<<"> ";
        out<<V[i].first.id<<" ";
    }*/
    cout<<endl;
    for(list <nod>::iterator it = L.begin(); it!=L.end(); ++it)
        out<<it->id<<" ";

}