Cod sursa(job #2406670)

Utilizator pasoi_stefanPasoi Stefan pasoi_stefan Data 16 aprilie 2019 01:45:09
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<queue>
#include<list>
using namespace std;
ifstream cin("sortaret.in");
ofstream cout("sortaret.out");

int n,m;
int dext[50005];

vector<int> G[50005];
vector<pair<int,int> > M;

queue<int> S;
list<int> L;

int compEdge(const pair<int,int> &i,const pair<int,int> &j){

    return i.first<j.first || i.first==j.first && i.second<j.second;

}

int eqEdge(const pair<int,int> &i,const pair<int,int> &j){

    return i.first==j.first && i.second==j.second;

}

int main(){

    cin>>n>>m;
    for(int i=1;i<=m;i++){

        int x,y;
        cin>>x>>y;

        M.push_back(make_pair(x,y));

    }

    sort(M.begin(),M.end(),compEdge);

    M.resize(distance(M.begin(),unique(M.begin(),M.end(),eqEdge)));

    for(int i=0;i<M.size();i++){

        ++dext[M[i].first];
        G[M[i].second].push_back(M[i].first);

    }

    for(int i=1;i<=n;i++)
        if(!dext[i]) S.push(i);

    while(!S.empty()){

        int x=S.front();
        S.pop();

        L.push_front(x);

        for(int i=0;i<G[x].size();i++){

            --dext[G[x][i]];
            if(dext[G[x][i]]==0)
                S.push(G[x][i]);
        }

    }

    for(list<int>::iterator it=L.begin();it!=L.end();it++)
        cout<<*it<<' ';

}