Zadanie
Jarné sústredenie KSP1 sa pomaly blíži a vedúci začali s prípravami. Prvou, vcelku dôležitou úlohou je pozvať účastníkov. Zobrali sa preto výsledkové listiny oboch kategorií a spojili sa do jednej, čím vznikol dlhý zoznam, podľa ktorého sa bude pozývať na sústredenie. Postupne sa budú oslovovať účastníci od prvého miesta po posledné, až kým prvých 32 účastníkov nepovie, že ide na sústredenie. Je preto jasné, že čím skôr je niekto v tomto zozname, tým má väčšiu šancu, že sa na sústredenie dostane.
To všetko by bolo pekné, vedúci však začali vyjadrovať svoje súkromné preferencie. Napríklad Mišo povedal, že Paulínka musí byť pozvaná skôr ako prvý človek v zozname, aby sa určite dostala na sústredenie. Žaba tiež vyjadril názor, že dievčatá by sa mali uprednostňovať a pozývať protekčne skorej. A Hopko nástojil2, aby bol jeho brat Slavo pozvaný na sústredenie skôr ako Andrej.
Aby v tom mala Baška prehľad, spísala si \(m\) požiadaviek vedúcich. Môže sa stať, že sa jedna požiadavka niekoľkokrát opakuje. Každá požiadavka je tvaru "x y"
a vyjadruje, že človek, ktorý je v zozname na \(x\)-tej pozícii má byť na sústredenie pozvaný skôr ako človek na \(y\)-tej pozícii. Baška sa teraz zamýšľa, v akom poradí má vlastne pozývať účastníkov z pôvodného zoznamu. Určite chce splniť všetky požiadavky, ktoré majú vedúci. Zároveň ale chce pozvať účastníka, ktorý je na prvom mieste čo najskôr. Z možných poradí, ktoré spĺňajú túto podmienku, chce potom vybrať také, kde pozve účastníka na druhom mieste čo najskôr atď…
Úloha
Máme \(n\) účastníkov očíslovaných \(1\) až \(n\) v poradí, v akom by sa mali pozývať na sústredenie. Ďalej máme \(m\) požiadaviek – dvojíc \(x_i\) a \(y_i\). Nájdite takú permutáciu čísel \(1\) až \(n\), že pre všetky \(i\) je číslo \(x_i\) pred číslom \(y_i\). Spomedzi takýchto permutácií vyberte tú, v ktorej je číslo \(1\) najskôr ako sa (za splnenia všetkých požiadaviek) dá, číslo \(2\) je najskôr ako sa (za splnenia všetkých predošlých podmienok) dá, a tak ďalej až po \(n\).
Formát vstupu
Na prvom riadku sa nachádzajú dve čísla \(n\) a \(m\) (\(1 \leq n \leq 200\,000\), \(1 \leq m \leq 400\,000\)) – počet účastníkov a počet požiadaviek. Nasleduje \(m\) riadkov, každý obsahuje dvojicu čísel \(x_i\) a \(y_i\) (\(1 \leq x_i, y_i \leq n\)).
Vstupné súbory sú pomerne veľké. Odporúčame preto používať C++ (keďže Python nemusí stíhať ani pri optimálnej časovej zložitosti) a na načítavanie odporúčame použiť knižnicu cstdio
.
Formát výstupu
Na jeden riadok vypíšte \(n\) medzerami oddelených čísel – permutáciu spĺňajúcu podmienky zo zadania. Je zaručené, že aspoň jedna takáto permutácia existuje.
Príklad
Input:
4 1
3 1
Output:
3 1 2 4
Účastníka 1 nevieme pozvať ako prvého, ale ak najskôr pozveme účastníka 3, tak ho môžeme pozvať už ako druhého. Následne chceme najskôr pozvať účastníka 2 a až potom 4.
Input:
5 6
3 1
5 1
5 2
1 4
5 4
3 1
Output:
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ž DAG1.
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'));
}
Z anglického Directed Acyclic Graph↩
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.