DSU

1. Põhimõisted

Graaf (graph) on struktuur, mis koosneb hulgast tippudest (vertices) ja tippe omavahel ühendavatest servadest (edges).

Graaf on sidus (connected), kui igast tipust leidub mööda servi teekond igasse teise tippu.

See graaf on sidus.

See graaf ei ole sidus — ei leidu teekonda 5 ja 13 vahel.

Alati võime graafi tükeldada sidususkomponentideks (connected component) — sidusateks komponentideks, kusjuures komponentide vahel servi pole.

2. Sidususe kontrollimise ülesanne

2.1. Ülesande püstitus

Ülesanne 1. On antud graaf $N$ tipuga, alguses servi pole. Tuleb $Q$ päringut:

$(+ \, u \, v)$ — tippude $u$ ja $v$ vahele lisandub serv;
$(? \, u \, v)$ — vastata, kas leidub teekond tipust $u$ tippu $v$?

$1 \le N, Q \le 10^5$.

Samaväärne ülesanne:

Ülesanne 2. On antud graaf $N$ tipuga, alguses servi pole. Tuleb $Q$ päringut:

$(+ \, u \, v)$ — tippude $u$ ja $v$ vahele lisandub serv;
$(? \, u \, v)$ — vastata, kas $u$ ja $v$ on samas sidususkomponendis?

$1 \le N, Q \le 10^5$.

2.2. Baaslahendus

Idee: igast tipust on nooleke mingisse tippu. Moodustuvad puud. Teeme nii, et need puud vastaksid täpselt sidususkomponentidele.

Meil on vaja ühelt poolt osata selle andmestruktuuri abil teist tüüpi päringutele vastata ja teiselt poolt osata seda andmestruktuuri uute servade lisandumise korral uuendada.

1 / 5

Probleem: selle algoritmi keerukus on $O(NQ)$, mis on liiga aeglane. Põhimõtteliselt on võimalik, et iga päring võtab $O(N)$ aega. Probleem tekib siis, kui osad puud muutuvad väga kõrgeks.

Seetõttu vajame ülesande efektiivseks lahendamiseks veel midagi. Allpool toome välja kaks meetodit, millest võib kasutada emba-kumba.

2.3. Optimisatsioon: union by rank

Idee: suuname puid ühendades noolekese alati madalama puu juurest kõrgema puu juurde. Näiteks tuleks suunata nii, nagu on näidatud alloleval parempoolsel pildil, aga mitte nii, nagu näidatud alloleval vasakpoolsel pildil.

See idee on võimsam, kui võiks arvata. Tasub arutleda nii: puu kõrgus saab kasvada ainult siis, kui me ühendame omavahel kaks sama kõrgusega puud. Nüüd paneme tähele:

Selleks, et teha puud kõrgusega 0, on vaja 1 tippu.
Selleks, et teha puud kõrgusega 1, on vaja kaht puud kõrgusega 0 ehk vähemalt 2 tippu.
Selleks, et teha puud kõrgusega 2, on vaja kaht puud kõrgusega 1 ehk vähemalt 4 tippu.
Selleks, et teha puud kõrgusega 3, on vaja kaht puud kõrgusega 2 ehk vähemalt 8 tippu.
...
Selleks, et teha puud kõrgusega 20, on vaja kaht puud kõrgusega 19 ehk vähemalt 1048576 tippu.

On kerge näha, et puud ei saa kunagi olla kõrgemad, kui $\log N$. Praktiliselt ainuke ajakulu kumbagi tüüpi päringute täitmisel oli mööda noolekesi puu juureni liikumine (kõik muu võtab alati sama palju aega), seega on nüüd iga päringu täitmise keerukus $O(\log N)$ ja kokku keerukus $O(Q \log N)$.

2.4. Optimisatsioon: path compression

Idee: raiskame palju aega, kui läheme iga kord mööda samu noolekesi üles. Kui peame üles minema, suuname pärast need läbitud noolekesed otse üles.

Path compression keerukuse analüüs on keerulisem ja tõestusi me selle loengu jooksul ei vaata. Optimisatsioonide keerukused võtab kokku järgmine tabel:

meetod	keerukus
mitte kumbki	$O(NQ)$
ainult union by rank	$O(Q \log N)$
ainult path compression	$O(Q \log N)$
union by rank ja path compression	$O(Q \alpha(N))

Siin $\alpha(N)$ on nn. Ackermanni funktsiooni pöördfunktsioon, mis on väga aeglase kasvuga; isegi $\alpha(10^{10^{100}}) < 5$.

3. Täiendava informatsiooni hoidmine DSU nooltel

Paljud ülesanded lahenduvad sarnasel viisil, aga DSU nooltel on vaja meeles pidada veel mingit informatsiooni. Teeme ühe sellise ülesande läbi ühel lihtsamal juhul.

Ülesanne 3. On antud graaf $N$ tipuga, alguses servi pole. Tuleb $Q$ päringut:

$(+ \, u \, v)$ — tippude $u$ ja $v$ vahele lisandub serv;
$(? \, u \, v)$ — vastata, kas leidub paaritu pikkusega teekond tipust $u$ tippu $v$?

$1 \le N, Q \le 10^5$.

Ülesande lahendamiseks vajame kahealuselise graafi mõistet.

Kahealuseliseks nimetatakse graafi, kus ei leidu paaritu pikkusega tsüklit. Samaväärselt võib kahealuselise graafi defineerida kui graafi, mille tipud saab värvida kahe värviga nii, et ükski serv ei ühenda sama värvi tippe.

Allolev graaf on kahealuseline: tipud on värvitud mustaks ja valgeks nii, et ükski serv ei ühenda sama värvi tippe.

Uurime, mis tingimustel leidub paaritu pikkusega teekond $u \leadsto v$.

Tähelepanek.

Kui $u$ ja $v$ on erinevates komponentides, siis teekonda ei leidu.
Kui $u$ ja $v$ on paaritu tsükliga komponendis, siis teekond leidub.
Kui $u$ ja $v$ on kahealuselises komponendis ja sama värvi, siis teekonda ei leidu.
Kui $u$ ja $v$ on kahealuselises komponendis ja eri värvi, siis teekond leidub.

Tõestus

Kui $u$ ja $v$ on erinevates komponentides, siis ei leidu nende vahel mingit teekonda, ammugi mitte paaritu pikkusega.
Olgu $u$ ja $v$ on paaritu tsükliga kompoenendis. Võtame mingi suvalise teekonna $u \leadsto v$. Kui see juba on paaritu pikkusega, siis on teekond leitud. Vastasel juhul võtame mingi paaritu pikkusega tsükli, olgu $x$ suvaline tipp sellel tsüklil. Sobiv teekond on siis $u \leadsto x \leadsto \mathrm{tsükkel} \leadsto x \leadsto u \leadsto v$, kus $u \leadsto x$ ja $x \leadsto u$ on sama teekond.
Olgu $u$ ja $v$ sama värvi, üldisust kitsendamata mõlemad valged. Mistahes teekonnal $u \leadsto v$ on värvid siis valge-must-valge-must-...-must-valge, seega läbitakse kindlasti alati paarisarv servi.
Analoogiline eelmise punktiga.

Seega on meil vaja täiendada union-find andmestruktuuri nii, et oskaksime tuvastada, kas kaks tippu on "sama värvi". Idee on järgmine: hoiame iga tipu kohta meeles, kas ta on oma vanemaga sama värvi (joonistel sinised nooled) või eri värvi (joonistel punased nooled).

1 / 4

Minimaalne toesepuu

1. Põhimõisted ja ülesande püstitus

Puuks nimetatakse sidusat tsükliteta graafi.

Olgu meil sidus graaf. Valime selle servade seast välja mõned servad nii, et nendest moodustuks puu, mis ühendab kõik graafi tipud. Mistahes niimoodi saadud puud nimetatakse toesepuuks (või aluspuuks).

Ülesanne 4. Olgu antud graaf, millel on $N$ tippu ja $M$ serva, kusjuures igal serval on mingi kaal. Leia selline toesepuu, millel on minimaalne kaal.

$1 \le N \le 10^5$, $1 \le M \le 2 \cdot 10^5$.

Näide ühe graafi minimaalsest toesepuust:

2. Kruskali algoritm minimaalse toesepuu leidmiseks

Võistlusprogrammeerimises kõige kasulikum algoritm toesepuu leidmise algoritm on nn Kruskali algoritm. On ka teisi, nt. Primi ja Boruvka algoritmid, aga praktika on näidanud, et enamus olukordades on Kruskali algoritm kõige mõistlikum; seda on ka väga lihtne implementeerida.

Algoritm ise on järgmine:

sorteerime servad kaalu järgi kasvavalt;
käime läbi kõik servad $uv$; iga serva kohta:
- kontrollime, kas $u$ ja $v$ on samas sidususkomponendis (kasutame DSU-d);
- kui ei ole, siis lisame vastusesse serva $uv$; seejuures kasutame jälle DSU-d, et nende vahele serva lisada.

1 / 30

Viimaks analüüsime algoritmi keerukust.

Sorteerimine võtab $O(M \log M)$.
Iga serva jaoks teeme üks või kaks DSU päringut; kokku $O(M)$ päringut ja keerukus seega $O(M \alpha(M))$.

Sorteerimine domineerib, seega on keerukus $O(M \log M)$.

DFS-puu

Järgmine tekst põhineb suuresti järgmisel blogil.

1. DFS-puu mõiste

Vaatleme suunamata sidusat graafi $G$. Jooksutame tema peal järgmist koodi:

function visit(u):
    visited[u] = 1
    for (üle kõigi u naabrite v):
       if (visited[v] == 0):
           märgistame serva uv
           kutsume visit(v)

Tegu on graafi $G$ sügavuti läbi käimisega. Animeeritult näeb visit(1) kutsumine välja järgmine:

Vaatleme real 5 märgstaitud servi. Nad moodustavad graafi $G$ toespuu, juurtipuga 1. Kutsume märgistatud servi toeservadeks (span-edge), ülejäänud servi naasvateks servadeks (back-edge, varasemalt olen kasutanud lisaserv).

Meie graafi DFS-puu näeb välja järgmine:

Tähelepanek. Iga DFS-puu naasev serv ühendab mingi tipu oma eellasega. See omadus on see, mis teeb DFS-puu kasulikuks.

Tõestus. Olgu antud serv $uv$; üldisust kitsendamata eeldame, et kui DFS läbib tippu $u$, on tipp $v$ veel läbimata. Vaatleme kaht juhtu.

DFS liigub tipust $u$ tippu $v$ mööda serva $uv$. Siis $uv$ on toeserv.
DFS ei liigu tipust $u$ tippu $v$ mööda serva $uv$. See tähendab, et kui real 4 seda kontrolliti, siis oli tipp $v$ juba külastatud. Järelikult külastati seda tipu $u$ mõne teise naabri külastamise käigus. Seega $u$ on $v$ eellane DFS-puus.

Seega ei saa $uv$ olla midagi muud peale toeserva ja serva, mis tippu eellasega ühendab.

Näiteks ülalolevas graafis ei saaks kuidagi tippude 4 ja 8 vahel olla naasvat serva, sest kumbki ei ole teise eellane. Kui tippude 4 ja 8 vahel oleks olnud serv, siis oleks sügavuti läbimise käigus tipust 4 tippu 2 naasmise asemel liigutud tippu 8.

2. Praktilised ülesanded

2.1. Ülesanne: sildade leidmine

Sillaks nimetatakse graafi serva, mille eemaldamisel graaf enam sidus ei ole.

Ülesanne 5. Olgu antud $n$ tipu ja $m$ servaga sidus suunamata graaf $G$. Leia graafi $G$ kõik sillad.

$1 \le n, m \le 10^5$.

Tähelepanek. Toeserv $uv$ on sild siis ja ainult siis, kui ei leidu naasvat serva, mis ühendab $uv$ mingit järglast $uv$ mingi eellasega. Teisisõnu, $uv$ on sild siis ja ainult siis, kui ei leidu naasvat serva, mis servast $uv$ "üle läheb".

Tõestus. Serva $uv$ eemaldamine lõhub toespuu kaheks sidususkomponendiks: $uv$ alampuu ja ülejäänud toespuu. Kui nende komponentide vahel on serv, siis on graaf sidus, vastasel juhul on $uv$ sild. Ainus viis, kuidas naasev serv need kaks sidususkomponenti ühendada saab on $uv$ eellase ühendamine $uv$ järglasega.

Näiteks ülaloleval graafil $6-2$ ei ole sild, kuna tema eemaldamisel naasev serv $3-8$ hoiab graafi koos. Seevastu $2-4$ on sild, kuna ükski naasev serv tema eemaldamisel graafi koos ei hoia.

Tähelepanek. Naasev serv ei ole kunagi sild.

Need kaks tähelepanekut on klassikalise servade leidmise meetodi aluseks. Sisendgraafi $G$ korral leiame sillad üles nii:

leiame graafi $G$ DFS-puu;
iga toeserva $uv$ korral kontrollime, kas leidub naasev serv, mis servast $uv$ "üle läheb"; kui ei ole, siis oleme leidnud silla.

DFS-puu lihtsa struktuuri tõttu ei ole sammu 2 keeruline teha. Üks klassikaline meetod on pidada meeles teatud massiivi $\mathrm{low}[u]$. Uute ideede tutvustamise eesmärgil teeme seekord teistmoodi. Olgu $\mathrm{dp}[u]$ naasvate servade arv, mis tipu $u$ ja tema vanema vahelisest servast "üle lähevad". Seda saab arvutada välja valemiga

\[ \mathrm{dp}[u] = (\text{tipust } u \text{ üles minev. naasv. servade \#}) - (\text{tipust } u \text{ alla minev. naasv. servade \#}) + \sum_{v \text{ on } u \text{ laps}} \mathrm{dp}[v]. \]

Kui $p$ on tipu $u$ vanem, siis $pu$ on sild parajasti siis, kui $\mathrm{dp}[u] = 0$.

2.2. Ülesanne: servade orienteerimine

Suunatud graafi nimetatakse tugevalt sidusaks, kui igast tipust on võimalik igasse tippu mööda suunatud servi liikuda.

Ülesanne 6. Olgu antud $n$ tipu ja $m$ servaga sidus suunamata graaf $G$. Määra kõikidele servadele suunad nii, et graaf muutuks tugevalt sidusaks (või teata, et see ei ole võimalik).

$1 \le n, m \le 10^5$.

Tähelepanek. Kui $G$ sisaldab sildu, siis see ei ole võimalik.

Tõestus. Oletame, et $uv$ on sild. Üldisust kitsendamata suuname selle $u \to v$. Siis aga ei saa kuidagi mööda suunatud servi liikuda tipust $v$ tippu $u$.

Edasises eeldame niisiis, et graafis ei ole sildu. Vaatleme tema DFS-puud. Suuname kõik toeservad "alla" ja kõik naasvad servad "üles".

Tähelepanek. Juurtipust leidub igasse tippu suunatud teekond.

Tõestus. Võime lihtsalt mööda toeservi alla liikuda.

Tähelepanek. Igast tipust leidub juurtippu suunatud teekond.

Tõestus. Olgu $v$ mingi tipp, mis ei ole juurtipp; olgu $u$ tema vanem DFS-puus. Et graafis ei ole sildu, siis peab leiduma mingi naasev serv, mis "läheb üle" toeservast $uv$. See naasev serv ühendab mingi $u$ eellase mingi $v$ järglasega. Võime liikuda mööda toeservi alla, kuni jõuame selle naasva serva alumise otspunktini. Seejärel liigume mööda toda naasvat serva üles. Nii oleme vähemalt ühe sammu juure suunas liikunud. Seda protsessi saab korrata, kuni jõuame juurtippu.

Nendest tähelepanekutest järeldub, et graaf on nüüd tugevalt sidus. Põhimõtteliselt on seda lahendust võimalik implementeerida ka ilma otseselt DFS-puud kasutamata. Samas oleks korrektsuse tõestamine (ja ehk ka lahenduse peale tulemine) äärmiselt tülikas.

2.3. Ülesanne: kolm sõltumatut teekonda

Ülesanne 7. Olgu antud $n$ tipu ja $m$ servaga sidus suunamata graaf $G$. Vali tipud $u$ ja $v$ ning leia kolm teekonda $u \leadsto v$ nii, et nendel teekondadel ei ole (paarikaupa) ühiseid tippe peale $u$ ja $v$ (või teata, et see ei ole võimalik).

$1 \le n, m \le 10^5$. [Allikas: CF 521 E]

Tähelepanek. Kui puu on kaktus (iga serv sisaldub ülimalt ühes lihttsüklis), siis see ei ole võimalik.

Tõestus. Oletame, et sellised kolm teekonda leiduvad ja tähistame nad $u a_1 a_2 \ldots a_{k_a} v$, $u b_1 b_2 \ldots b_{k_b} v$ ja $u c_1 c_2 \ldots c_{k_c} v$. Võime eeldada, et need teekonnad ei läbi ühtki tippu mitu korda. Saame kaks erinevat lihttsüklit

\[ u a_1 a_2 \ldots a_{k_a} v b_{k_b} \ldots b_2 b_1 u \text{ ja } u a_1 a_2 \ldots a_{k_a} v c_{k_c} \ldots c_2 c_1 u. \]

Nendel on ühine serv $u a_1$, seega graaf ei saa olla kaktus.

Ülejäänud juhtudel on see võimalik. Eeldame, et puu ei ole kaktus. Kasutame DFS-puud, et sellised kolm teekonda leida. Loendame iga toeserva jaoks, mitu naasvat serva temast "üle läheb" (seda õppisime sildade leidmise juures tegema). Leidub vähemalt üks toeserv $st$, millest "läheb üle" kaks erinevat naasvat serva $ab$ ja $cd$ (veenduda, et vastasel juhul on tegu kaktusega). Üldisust kitsendamata eeldame, et $a$ on $b$ eellane, $c$ on $d$ eellane ning $a$ on $c$ eellane. Olgu $l = \mathrm{lca}(b, d)$.

Võtame $u = c$ ja $v = l$. Kolm sõltumatut teekonda on:

$u = c d \leadsto l = v$ ($d \leadsto l$ on üles mööda toeservi);
$u = c \leadsto a b \leadsto l = v$ ($c \leadsto a$ ja $b \leadsto l$ on mõlemad üles mööda toeservi);
$u = c \leadsto l = v$ (alla mööda toeservi);

Alljärgneval joonisel on need kolm teekonda märgitud kolme eri värviga.

meetod	keerukus
mitte kumbki	\(O(NQ)\)
ainult union by rank	\(O(Q \log N)\)
ainult path compression	\(O(Q \log N)\)
union by rank ja path compression	$O(Q \alpha(N))