Cod sursa(job #3342400)

Utilizator DoltuVladDoltu Vlad DoltuVlad Data 24 februarie 2026 08:26:46
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <vector>
#define NMAX 100005
using namespace std;
ifstream cin("topsort.in");
ofstream cout ("topsort.out");
int n,x,y,nrniv,m;
vector<int>g[NMAX];
vector<int>niv[NMAX];
int di[NMAX];

void citire()
{
    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {cin>>x>>y;
        ///daca am arc de la x la y
        g[x].push_back(y);
        di[y]++;
    }
}

void descompunere_pe_niveluri()
{
    int total=0;
    while (total<n) ///ai am varfuri de reartizat pe niveluri
    {
        ///pe nivelul curent plasam toate varfurile x cu di[x]=0
        for (int x=1; x<=n; x++)
            if (di[x]==0)
                niv[nrniv].push_back(x);
        ///pentru tate varfurile de pe nivelul curent trebuie sa le elimin logic si sa decrementez di pentru vecnii lor
        for (int i=0; i<niv[nrniv].size(); i++)
        {
            x=niv[nrniv][i];
            di[x]=-1;   ///l am eliminat logic
            ///parcurg lista de adiacenta a lui x
            for (int j=0; j<g[x].size(); j++)
                di[g[x][j]]--;
        }
        total+=niv[nrniv].size();
        nrniv++;
    }
}

void afisare()
{
    //cout<<nrniv<<endl;
    for (int i=0;i<nrniv;i++)
    {
        for (int j=0;j<niv[i].size();j++)
            cout<<niv[i][j]<<' ';
        cout<<endl;
    }
}

int main()
{
    citire();
    descompunere_pe_niveluri();
    afisare();
    return 0;
}