Cod sursa(job #2471446)

Utilizator Catalin2002Catalin Craciun Catalin2002 Data 10 octombrie 2019 21:48:06
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

queue <int> coada;

struct data{

int i;
int val;

}w[50001];

bool cmp(data a,data b)
{
    return a.val<b.val;
}

int main()
{
    int n,m,x,i,j,y;

    fin>>n>>m;

    vector<int> v[n+1];

    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        v[x].push_back(y);
    }


    for(i=1;i<=n;i++)
    {
        coada.push(i);

        while(!coada.empty())
        {
            x=coada.front();
            w[x].val++;
            coada.pop();

            for(j=0;j<v[x].size();j++)
            {
                coada.push(v[x][j]);
            }

        }

    }


    for(i=1;i<=n;i++)
        w[i].i=i;

    std::sort(w+1,w+1+n,cmp);

    for(i=1;i<=n;i++)
        fout<<w[i].i<<" ";


    return 0;
}