Cod sursa(job #3237406)

Utilizator Bolfa_DBolfa Diana Bolfa_D Data 8 iulie 2024 20:58:44
Problema Sortare topologica Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>
#define NMAX 50050
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
set<int> s[NMAX];
int n,m,x,y, v[NMAX],g[NMAX],k;
deque<int> q;
int main()
{
    fin>>n>>m;

    for(int i=1;i<=m;++i)
    {
        fin>>x>>y;
        s[x].insert(y);
        ++g[y];
    }

    for(int i=1;i<=n;++i)
        if(g[i]==0)
        {
            q.push_back(i);
            v[++v[0]]=i;
        }

    while(q.empty()==false)
    {
        k=q.front();
        q.pop_front();

        for(auto i:s[k])
        {
            --g[i];
            if(g[i]==0)
            {
                q.push_back(i);
                v[++v[0]]=i;
            }
        }
    }

    for(int i=1;i<=n;++i)
        fout<<v[i]<<" ";

    return 0;
}