Cod sursa(job #3303940)

Utilizator SimifilLavrente Simion Simifil Data 19 iulie 2025 12:58:44
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <vector>
#include <deque>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
const int maxn = 50000;
vector<int> v[maxn+1];
int grad[maxn+1][2];

int main() {
    ios_base::sync_with_stdio(false);
    f.tie(nullptr);
    g.tie(nullptr);

    int n, m;
    f >> n >> m;
    for( int i = 1; i <= m; ++i )
    {
        int x, y;
        f >> x >> y;
        v[x].push_back(y);
        ++grad[x][1];
        ++grad[y][0];
    }
    deque<int> q;
    vector<int> ans;
    for( int i = 1; i <= n; ++i )
    {
        if( grad[i][0] == 0 )
        {
            q.push_back( i );
            ans.push_back( i );
        }
    }
    while( q.empty() == false )
    {
        int parinte = q.front();
        q.pop_front();
        for( int copil = 0; copil < v[parinte].size(); ++copil )
        {
            --grad[ v[parinte][copil] ][0];
            if( grad[ v[parinte][copil] ][0] == 0 )
            {
                ans.push_back( v[parinte][copil] );
                q.push_back( v[parinte][copil] );
            }
        }
    }
    for( int x = 0; x < ans.size(); ++x )
        g << ans[x] << " ";
    

    return 0;
}