Cod sursa(job #3003122)

Utilizator Luka77Anastase Luca George Luka77 Data 15 martie 2023 14:50:43
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>
using namespace std;

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

const int NMAX = 50005;
int n, m;
bool exista[NMAX], viz[NMAX];
int parents[NMAX], act[NMAX];
vector<int>g[NMAX];
queue<int>q;

int main()
{
    fin >> n >> m;

    for(int i = 1; i <= m; ++ i)
    {
        int x, y;
        fin >> x >> y;
        g[x].push_back(y);
        parents[y]++;
        exista[y] = 1;
    }

    for(int i = 1; i <= n; ++ i)
        if(!exista[i])
            q.push(i), viz[i] = 1, cout << i << '\n';

    while(!q.empty())
    {
        int node = q.front();
        q.pop();
        fout << node << ' ';
        for(auto new_node : g[node])
        {
            act[new_node]++;
            if(parents[new_node] == act[new_node])
            {
                if(!viz[new_node])
                {
                    viz[new_node] = 1;
                    q.push(new_node);
                }
            }
        }
    }
}