4. Starček skazil spojenie vzorové riešenie

4 4
1 2
2 3
1 3
3 4
3
2 4 3

1 2 3

3 1
1 2
1
1

3

Pomalé riešenie

Prvé riešenie, ktoré nám môže napadnúť je, že začneme s grafom zo vstupu a potom z neho odstraňujeme hrany a počítame komponenty.
Skúsme sa pozrieť na časovú zložitosť takéhoto riešenia. Graf si vieme vytvoriť v čase \(O(n+m)\).
Poďme teraz na odstraňovanie hrán. Pre každú odstránenú hranu vieme pomocou BFS/DFS spočítať počet komponentov. Takéto BFS/DFS musí prejsť prinajhoršom cez všetky hrany, takže jeho zložitosť bude \(O(n+m)\).
My ho chceme vykonať pre \(q\) odstránených hrán, čo nám dá zložitosť \(O(q \cdot (n+m))\).
Oproti tomuto je \(O(m)\) zanedbateľné, takže celková časová zložitosť by bola \(O(q \cdot (n+m))\).

Malé vylepšenie

V skutočnosti ale nepotrebujeme rátať komponenty pri každom odstránení hrany. Stačí, ak ich spočítame na začiatku, a keď odstránime hranu, pozrieme sa či vrcholy, ktoré spájala zostanú v rovnakom komponente, alebo sa rozdelia na dva.
Týmto síce časovú zložitosť nezmeníme (stále používame BFS/DFS čo má zložitosť \(O(n+m)\)), lebo v najhoršom prípade budeme stále potrebovať prejsť celý graf, ale v priemere bude tento spôsob o niečo rýchlejší. Je to tak preto, lebo v predchádzajúcom prípade sme vždy museli prejsť celý graf, zatiaľ čo tu budeme väčšinou prechádzať iba určitú časť grafu.

Union-find

Pomalé riešenie s vylepšením nám už môže trošku začať pripomínať union-find.
O union-finde sme viac hovorili v predošlej úlohe, takže ak ho nepoznáte, odporúčame vám pozrieť si jej vzorové riešenie.

Skúsme si túto úlohu preformulovať, aby sme vedeli priamo aplikovať union-find. Namiesto odoberania hrán ich môžme skúsiť v opačnom poradí pridávať. Začneme tými hranami, ktoré nikdy nebudú odstránené. Potom budeme postupne hrany, ktoré by sme odoberali, pridávať v opačnom poradí.

Ako sem ale zakomponujeme počítanie komponentov?
Vieme, že graf bez hrán, ktorý má \(n\) vrcholov začína s \(n\) komponentami (každý vrchol je v samostatnom komponente). V union-finde máme operáciu, ktorá nám spojí dva vrcholy do jedného komponentu, ak boli v rozličných. Do tejto funkcie vieme jednoducho implementovať to, že keď dva vrcholy skutočne spojí, zníži počítadlo komponentov o 1.

Tým pádom vieme po každom odstránení (čo je to isté ako pred pridaním) hrany povedať, koľko komponentov máme v grafe.

Ešte sa ale musíme vrátiť k jednej časti. Ako zistíme, ktoré hrany budú odstránené a ktoré nie?
Prvé riešenie, ktoré nám môže napadnúť by sme sa jednoducho pre každú hranu pozreli či bude odstránená. To je ale pomalé s časovou zložitosťou \(O(m \cdot q)\).
V skutočnosti to vieme urobiť oveľa rýchlejšie s časovou zložitosťou \(O(m + q \cdot \log_{2}{q})\). Dosiahneme to tak, že si najprv usporiadame odstránené hrany podľa ich poradových čísel. Potom budeme postupne prechádzať hranami a pri každej sa pozrieme, či sa nachádza na začiatku tohto zoznamu. Ak áno, tak vieme, že bude niekedy odstránená a tento prvok odstránime zo začiatku zoznamu. Z tohto a toho, že budeme hranami postupne prechádzať (takže od najmenšieho čísla po najväčšie) vyplýva aj to, že sa nikdy nemusíme pozrieť na iný ako prvý prvok zoznamu (prvý bude vždy najmenší ku ktorému sme sa ešte nedostali).

Zložitosti

Časová zložitosť

Začnime s tým, že sa pozrieme koľko operácií s union-findom vykonáme.
Každú hranu pridáme do grafu práve raz a tento graf bude mať \(n\) vrcholov, takže dostávame časovú zložitosť union-findu \(O(m \cdot \alpha(n))\).
\(\alpha(n)\) je inverzná Ackermanova funkcia - funkcia ktorá rastie veľmi pomaly.

Teraz sa potrebujeme pozrieť na to, ako vytriediť hrany, ktoré nikdy nebudú odstránené od ostatných. Prvá časť, triedenie zaberie \(O(q \cdot \log_{2}{q})\) času a druhá, postupné prechádzanie hrán zaberie \(O(m)\). To nám dáva dokopy časovú zložitosť \(O(m + q \cdot \log_{2}{q})\).

Tým sa dostávame k celkovej časovej zložitosti programu \(O(m \cdot \alpha(n) + q \cdot \log_{2}{q})\).
Z časovej zložitosti zmizne \(m\), lebo nie je v porovnaní s \(m \cdot \alpha(n)\) dôležité, keďže \(\alpha(n)\) je vždy väčšie ako \(1\).

Pamäťová zložitosť

Pamäťová zložitosť je o niečo jednoduchšia. Union-find potrebuje \(O(n)\) pamäte, zapamätanie si hrán na vstupe je \(O(m)\) a zapamätanie odstránených hrán je \(O(q)\). Ešte si budeme potrebovať pamätať aj výstup, keďže ho potrebujeme vypísať v opačnom poradí, ale to je tiež \(O(q)\).

Celková pamäťová zložitosť teda bude \(O(n+m+q)\).

Implementácia

Začnime s implementovaním union-findu. Ak chcete vidieť kompletný postup jeho implementácie, pozrite si vzorové riešenie úlohy z minulej série. Jediná modifikácia, ktorú oproti klasickému union-findu urobím je, že pridáme počítadlo komponentov, ktoré začína ako \(n\) a vždy keď dva komponenty spojíme, zníži sa o \(1\).

n, m = list(map(int, input().split()))

rodic = [i for i in range(n)]
rad = [0 for i in range(n)]
komponenty = n

def najdi_reprezentanta(v):
    if v == rodic[v]:
        return v
    else:
        reprezentant = najdi_reprezentanta(rodic[v])
        rodic[v] = reprezentant 
        return reprezentant

def spoj(x, v):
    x = najdi_reprezentanta(x)
    y = najdi_reprezentanta(y)

    if x == y:
        return
    
    if rad[x] < rad[y]:
        rodic[x] = y
    elif rad[x] > rad[y]:
        rodic[y] = x
    else:
        rodic[y] = x
        rad[x] += 1
    
    # jedným zo spôsobov vyššie sme spojili dve komponenty, takže ich je dokopy o jeden menej
    komponenty -= 1

Môžeme pokračovať tým, že si načítame zo vstupu hrany. Pre zjednodušenie budúcej práce s vrcholmi, odpočítame od každého vrcholu 1 (aby boli číslované od 0 ako sú aj polia a nie od 1).

hrany = []
for i in range(m):
    a, b = list(map(int, input().split()))
    hrany.append((a-1, b-1))

Ďalej načítajme hrany, ktoré odstránime. Aj od týchto indexov odčítame 1 z rovnakého dôvodu ako predtým.
V tej istej časti kódu môžeme zahrnúť aj vytváranie kópie tohto zoznamu a jej triedenie.
Dôvod, prečo nám nestačí utriediť pôvodný zoznam, ale potrebujeme kópiu je jednoduchý. Keby sme ho iba utriedili, stratili by sme tým pôvodné poradie, ktoré budeme ešte potrebovať pre vyriešenie úlohy.
Posledná vec, ktorú tu urobíme bude to, že obrátime poradie odstránených hrán.

q = int(input())
odstranene = []
for e in input().split():
    odstranene.append(int(e)-1)

odstranene_zoradene = odstranene.copy()
odstranene_zoradene.sort()

odstranene.reverse()

Teraz je čas pridať do grafu všetky hrany, ktoré nebudú odstránené.
Táto implementácia sa bude trochu líšiť od tej popísanej vyššie. Namiesto odstraňovania zo začiatku si budeme pamätať index, na ktorom sa aktuálne nachádzame. Je to v podstate akoby sme si presúvali to, čo považujeme za začiatok (čo je v podstate to isté, ako postup ktorý sme popísali predtým).

j = 0
for i in range(m):
    if j < q and odstranene_zoradene[j] == i:
        j += 1
    else:
        spoj(hrany[i][0], hrany[i][1])

Už nám zostáva iba postupne pridávať naspäť hrany v opačnom poradí, ako by mali byť odstraňované. Pred každým pridaním hrany si ale zapamätáme počet komponentov grafu (čo je efektívne ten istý moment ako po tom, čo by sme danú hranu odstránili).
Nesmieme však zabudnúť na to, že náš výstup bude v opačnom poradí, keďže tak aj prechádzame hranami, takže ho musíme ešte ored vypísaním “otočiť”.

vysledok = []
for i in range(q):
    vysledok.append(komponenty)
    spoj(hrany[odstranene[i]][0], hrany[odstranene[i]][1])

for e in reversed(vysledok):
    print(e, end=' ')

print()

Hotový program

n, m = list(map(int, input().split()))

rodic = [i for i in range(n)]
rad = [0 for i in range(n)]
komponenty = n

def najdi_reprezentanta(v):
    if v == rodic[v]:
        return v
    else:
        reprezentant = najdi_reprezentanta(rodic[v])
        rodic[v] = reprezentant 
        return reprezentant

def spoj(x, v):
    x = najdi_reprezentanta(x)
    y = najdi_reprezentanta(y)

    if x == y:
        return
    
    if rad[x] < rad[y]:
        rodic[x] = y
    elif rad[x] > rad[y]:
        rodic[y] = x
    else:
        rodic[y] = x
        rad[x] += 1
    
    komponenty -= 1

hrany = []
for i in range(m):
    a, b = list(map(int, input().split()))
    hrany.append((a-1, b-1))

q = int(input())
odstranene = []
for e in input().split():
    odstranene.append(int(e)-1)

odstranene_zoradene = odstranene.copy()
odstranene_zoradene.sort()

odstranene.reverse()

j = 0
for i in range(m):
    if j < q and odstranene_zoradene[j] == i:
        j += 1
    else:
        spoj(hrany[i][0], hrany[i][1])

vysledok = []
for i in range(q):
    vysledok.append(komponenty)
    spoj(hrany[odstranene[i]][0], hrany[odstranene[i]][1])

for e in reversed(vysledok):
    print(e, end=' ')

print()

Implementácia v C++

Postup implementácie pre C++ je úplne rovnaký, nebudeme ho teda opakovať.
Hlavný rozdiel v C++ oproti Pythonu je, že je rýchlejši ako Python, preto je väčšinou preferovaný pri algoritmických úlohách (ako bola napr. táto). Ostatné rozdiely sú primárne v syntaxi C++.

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

vector<int> rodic;
vector<int> rad;
int komponenty;

int najdi_reprezentanta(int x) {
    if (rodic[x] == x) {
        return x;
    } else {
        return rodic[x] = najdi_reprezentanta(rodic[x]);
    }
}

void spoj(int x, int y) {
    x = najdi_reprezentanta(x);
    y = najdi_reprezentanta(y);

    if (x == y) {
        return;
    }

    if (rad[x] < rad[y]) {
        rodic[x] = y;
    } else if (rad[x] > rad[y]) {
        rodic[y] = x;
    } else {
        rodic[y] = x;
        rad[x]++;
    }

    komponenty--;
}

int main() {
    int n, m;
    cin >> n >> m;

    rodic.resize(n);
    rad.resize(n);
    komponenty = n;

    for (int i = 0; i < n; i++) {
        rodic[i] = i;
        rad[i] = 0;
    }

    auto hrany = new pair<int, int>[m];

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        
        hrany[i] = {a-1, b-1};
    }

    int q;
    cin >> q;
    vector<int> odstranene(q);
    vector<int> odstraneneZoradene(q);

    for (int i = 0; i < q; i++) {
        cin >> odstranene[q - i - 1];
        odstranene[q - i - 1]--;
        odstraneneZoradene[q - i - 1] = odstranene[q - i - 1];
    }

    sort(odstraneneZoradene.begin(), odstraneneZoradene.end());

    int j = 0;
    for (int i = 0; i < m; i++) {
        if (j < q && odstraneneZoradene[j] == i) {
            j++;
        } else {
            spoj(hrany[i].first, hrany[i].second);
        }
    }

    int* vysledok = new int[q];

    for (int i = 0; i < q; i++) {
        vysledok[i] = komponenty;
        spoj(hrany[odstranene[i]].first, hrany[odstranene[i]].second);
    }

    for (int i = 0; i < q; i++) {
        cout << vysledok[q - i - 1];
        if (i != q - 1) {
            cout << " ";
        }
    }

    cout << endl;
}