6. O sústredkových pozvánkach vzorové riešenie

4 1
3 1

3 1 2 4

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

3 5 1 2 4

Keďže zadanie je trochu komplikovanejšie, začnime tým, že si ho zopakujeme. Máme čísla 1 až \(n\) a \(m\) podmienok, ktoré musíme splniť. Každá podmienka nám o nejakom čísle hovorí, že sa vo výslednej permutácii musí objaviť pred ktorýmsi iným číslom. Naviac, nechceme nájsť ľubovoľnú permutáciu, ktorá spĺňa všetky podmienky, ale takú, kde sa číslo 1 nachádza čo najskôr, potom číslo 2 čo najskôr atď. Uvedomme si, že toto nie je to isté ako hľadať lexikograficky najmenšiu takúto permutáciu, lebo permutácia \((3,1,2)\) je síce lexikograficky väčšia ako \((2,3,1)\), ale číslo 1 sa v nej nachádza skôr.

Pri riešení takýchto úloh je dobré si vstup zakresliť, aby sa nám nad ním lepšie rozmýšľalo – napríklad formou orientovaného grafu. Každé číslo bude mať priradený jeden vrchol a hrana povedie z vrchola \(x\) do vrchola \(y\), ak má byť \(x\) v permutácii pred \(y\). Keďže zadanie nám zaručuje, že existuje aspoň jedna vhodná permutácia, v takomto grafe sa nemôžu nachádzať orientované cykly (rozmyslite si prečo by sme ich nevedeli celé splniť) a takýto graf sa preto volá orientovaný acyklický graf, alebo tiež DAG¹.

Poďme sa teraz pozrieť na to, ako by sme vedeli vytvoriť vhodnú permutáciu, ktorá by spĺňala všetky podmienky. Ktoré číslo sa môže nachádzať na prvom mieste? Každé, ktoré nemá byť predbehnuté iným číslom. Keď sa teda pozrieme na náš graf, zistíme, že sú to tie vrcholy, do ktorých nevedie žiadna hrana – hrana vedie z vrchola, ktorý má byť skôr, do takého, ktorý má byť neskôr. Ak do vrchola vedie hrana, musíme najskôr do permutácie vložiť prvok na začiatku tejto hrany.

Ak teda vyberieme nejaké číslo a vložíme ho do permutácie, z nášho grafu si môžeme príslušný vrchol odstrániť. A rovnako všetky hrany, ktoré z neho viedli von, lebo tieto hrany už určite budú splnené. Ich začiatok sa v permutácii nachádza skôr ako ich koniec. Na druhom mieste permutácie môže byť opäť ľubovoľný vrchol, do ktorého nevchádza žiadna hrana.

Postupne by sme teda vedeli vytvoriť permutáciu, ktorá spĺňa všetky podmienky. Ako však vyberieme takú, kde bude 1 čo najskôr? Nemôžeme sa rozhodovať podľa veľkosti čísel, lebo nejaké väčšie číslo nám možno odkryje lepšie menšie a vie nastať pomerne veľa komplikovaných prípadov.

Keď to teda nevyšlo pre začiatok, skúsme vytvárať permutáciu od konca. Ktoré čísla môžu byť na poslednej pozícii? No predsa všetky, po ktorých už nemusí ísť žiadne číslo. V grafe sú to teda vrcholy, z ktorých nevychádza žiadna hrana. A opäť, ak si niektorý z nich vyberieme a odstránime ho z grafu, dostaneme graf, z ktorého môžeme vyberať číslo na pozíciu, ktorá je druhá od konca. Robíme v podstate to isté, len opačným smerom. Vieme však teraz zaručiť aj zvyšné požiadavky, teda aby sa 1 nachádzala vo výslednej permutácií čo najskôr?

Čo keby sme vždy z čísel, ktoré máme k dispozícii na poslednú pozíciu vybrali to, ktoré je najväčšie? Znie to ako nápad, ktorý nič nepokazí. Predsalen, umožníme všetkým menším číslam, aby sa nachádzali skôr. A síce je fajn, že nám intuícia napovedá, že tento postup je správny, musíme si ho aj dokázať.

Predstavme si, že máme optimálnu permutáciu, ktorá na posledné miesto umiestnila číslo \(x\), ale na posledné miesto môže ísť aj číslo \(y\), ktoré je väčšie ako \(x\). Čo sa stane, ak z tejto permutácie vyberieme číslo \(y\) a dáme ho na koniec, pričom všetky čísla, čo boli pôvodne za ním posunieme o jedno dopredu? Vo výslednej permutácii sa dozadu posunulo iba číslo \(y\). Všetky ostatné buď zostali na svojom mieste, alebo sa posunuli dopredu. A hlavne sa dopredu posunulo číslo \(x\). A keďže je menšie ako \(y\), tak táto permutácia je lepšie ako pôvodná, s ktorou sme začínali. To je ale spor s tým, že tá permutácia mala byť optimálna. Dokázali sme teda, že náš postup je správny.

Otázkou zostáva už len to, ako takéto riešenie naprogramovať. Musíme vedieť odstrániť ľubovoľný vrchol z grafu a tiež všetky hrany, ktoré z neho viedli. Takisto si musíme udržiavať množinu čísel, z ktorých nevedie žiadna hrana a z tejto množiny rýchlo vybrať číslo, ktoré je najväčšie. Na druhú časť použijeme dátovú štruktúru halda, do ktorej vieme vkladať prvok v čase \(O(\log n)\) a vyberať najväčší prvok v čase \(O(\log n)\), kde \(n\) je počet prvkov v halde.

Na začiatku načítame vstup a pre každý vrchol vytvoríme zoznam hrán, ktoré doň vchádzajú. Takisto si v poli \(P[]\) budeme pamätať, koľko hrán z neho vychádza. Všetky čísla \(x\), pre ktoré je \(P[x]\) rovné 0 vložíme do haldy, keďže sú to vrcholy, z ktorých nevychádza žiadna hrana. Z haldy vyberieme najväčšie číslo, označme si ho ako \(x\). Vrchol \(x\) chceme odstrániť z grafu. Preto prejdeme všetky hrany vychádzajúce z tohto vrchola a každému koncovému vrcholu zmenšíme hodnotu v \(P[]\), lebo už z neho vychádza o jednu hranu menej. Ak počas týchto úprav klesne niektoré \(P[y]\) na nulu, tak \(y\) vložíme do haldy. Na konci vypíšeme čísla v obrátenom poradí ako sme ich vyberali z haldy.

Každý vrchol vložíme aj vyberieme z haldy najviac raz. Takisto raz odstránime každú hranu. Preto je výsledná časová zložitosť tohto riešenia \(O(n\log n + m)\). Pamäťová zložitosť je \(O(n+m)\).

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;

#define For(i, n) for(int i=0; i<int(n); i++)

vector<vector<int> > G;
vector<int> P;
int n, m;

int main() {
  scanf("%d %d", &n, &m);
  P.resize(n, 0);
  G.resize(n);
  For(i, m) {
    int x, y;
    scanf("%d %d", &x, &y);
    x--; y--;
    G[y].push_back(x);
    P[x]++;
  }
  vector<int> Res;
  priority_queue<int> Q;
  For(i, n)
    if(P[i] == 0) 
      Q.push(i);
  while(!Q.empty()) {
    int v = Q.top(); Q.pop();
    Res.push_back(v);
    For(i, G[v].size()) {
      int w = G[v][i];
      P[w]--;
      if(P[w] == 0) Q.push(w);
    }
  }
  reverse(Res.begin(), Res.end());
  For(i, Res.size()) 
    printf("%d%c", Res[i]+1, ((i != Res.size()-1) ? ' ' : '\n'));
}