Rezolvare completă PbInfo #2768 SortTopMinLex

Cerința

Se consideră un graf orientat aciclic cu n noduri și m arce. Să se determine sortarea topologică a nodurilor grafului, minimă lexicografic.

Date de intrare

Programul citește de la tastatură numerele n și m, iar apoi m perechi de numere naturale, separate prin spații, x y cu semnificația: există în graful orientat arcul (x, y).

Date de ieșire

Programul va afișa pe ecran, separate prin câte un spațiu, nodurile grafului în ordinea lexicografică a acestora.

Restricții și precizări

  • 1 ≤ n ≤ 100.000
  • 1 ≤ m ≤ 500.000
  • Este garantat că graful orientat este aciclic, deci va exista o soluție

Exemplu

Intrare

6 7
3 6
3 1
6 1
5 1
2 5
4 1
4 2

Ieșire

3 4 2 5 6 1

Explicație

Digraful din exemplu este cel de mai jos.

Există mai multe soluții, precum 4,3,6,2,5,1, dar această soluție este mai mare din punct de vedere lexicografic.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema SortTopMinLex:

#include <bits/stdc++.h>
#define Nmax 100005
using namespace std;

vector<int> L[Nmax];
int n, m;
set<int> S;
/// in S se depun nodurile de grad interior 0
int d[Nmax]; /// d[i]=gradul interior al nodului i

void Citire()
{
    int i, x, y;
    cin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        cin >> x >> y;
        L[x].push_back(y);
        d[y]++;
    }
}

void SortTop()
{
    int i, nod;
    /// punem in S toate nodurile de grad 0
    for (i = 1; i <= n; i++)
        if (d[i] == 0)
            S.insert(i);
    while (S.size() > 0)
    {
        /// extrag din S nodul minim
        nod = *(S.begin());
        /// sterg nodul din stiva:
        S.erase(nod);
        cout << nod << " ";
        /// parcurgem lista de adiacenta a nodului nod
        /// si decrementam gradele tuturor nodurilor adiacente cu nod
        for (auto j : L[nod])
        {
            d[j]--;
            if (d[j] == 0)
                S.insert(j);
        }
    }
}

int main()
{
    Citire();
    SortTop();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #2768 SortTopMinLex

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2768 SortTopMinLex de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!