Cod sursa(job #2790696)

Utilizator AndreiCroitoruAndrei Croitoru AndreiCroitoru Data 29 octombrie 2021 13:05:56
Problema Sortare topologica Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;
vector <int> v[50001];
queue <int> q;
int deg[50000];
int main()
{
    ifstream cin("sortaret.in");
    ofstream cout("sortaret.out");

    int n, m;
    cin >> n >> m;
    for ( int i = 1; i <= m; i ++ )
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        deg[b] ++;
    }
    for ( int i = 1; i <= n; i ++)
    {
        if(deg[i] == 0)
        {
            q.push(i);
            cout << i << " ";
        }
    }
    while(!q.empty())
    {
        int aux = q.front();
        q.pop();
        if(deg[aux] == 0)
        {
            for(auto x: v[aux])
            {
                deg[x]--;
                if(deg[x] == 0)
                {
                    q.push(x);
                    cout << x << " ";
                }
            }
        }
    }
/*
    for ( int x = q.front() ; x<=q.back();x ++)
    {
        cout << x << " ";
    }*/
return 0;
}