Cod sursa(job #3366168)

Utilizator proflaurianPanaete Adrian proflaurian Data 29 septembrie 2026 17:11:41
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
const int N = 100010;
int n,m,gi[N],s[N],t=0,b=1; /// t=top=unde am adaugat ultimul nod in sirul sortat b=bottom= de unde iau urmatorul nod neprocesat
vector<int> v[N];
int main()
{
    f>>n>>m;

    for(int i=1;i<=m;i++)
    {
        int x,y;
        f>>x>>y;
        v[x].push_back(y);
        gi[y]++;
    }
    for(int i=1;i<=n;i++)
        if(gi[i]==0)
        {
            t++;
            s[t]=i;
        }
    while(t<n) /// cat timp nu am pus toate cele n noduri
    {
        int nod=s[b]; /// alege ultimul nod neprocesat dar care a ajuns in sir
        b++; /// trec la urmatorul nod care va fi procesat in viitor
        for(auto vec:v[nod])
        {
            gi[vec]--;/// scade o unitate din gradul interior al fiecarui vecin
            if(gi[vec]==0)/// daca un vecin ajunge la grad de intrare 0 se aduga in sirul de noduri sortat topologic
            {
                t++;
                s[t]=vec;
            }
        }
    }
    /// afisam sirul de noduri sortat topologic
    for(int i=1;i<=n;i++)
        g<<s[i]<<' ';
    g<<'\n';
    return 0;
}