Z řešení úlohy domácího kola plyne, že libovolný vrchol může být ten poslední, který odstraňujeme. Je tedy přirozené si vybrat jeden vrchol v, který si necháme nakonec, a v něm strom zakořenit. Dále si všimněme, že v každém kroku odstraňujeme list, protože odstraněním vrcholu, který není listem, by se strom rozpadl na více komponent souvislosti. Proto pro každý podstrom s kořenem u musíme odstranit jako poslední z tohoto podstromu právě vrchol u.
Označme pv(u) počet pořadí vrcholů podstromu s kořenem u vzhledem k zakořenění ve v, ve kterých lze vrcholy tohoto podstromu odstraňovat, aniž by byla porušena jeho souvislost a poslední byl odstraněn u. Výsledek úlohy získáme tak, že sečteme hodnoty pv(v) pro všechny možné volby posledního odebraného vrcholu v.
Jak ale spočítáme pv(u)? Pokusíme se o to rekurzivním algoritmem. Nechť u je libovolný vrchol stromu a u1, …, uk jeho synové. Nechť ni pro i=1,…,k označuje počet vrcholů v podstromu zakořeněném v ui a n=n1+…+nk. Odstranění podstromu pod u probíhá tak, že nejprve odstraníme všechny podstromy synů u a pak odstraníme u. Přitom pořadí odstraňování v jednotlivých podstromech synů do sebe můžeme libovolně míchat. Volbu pořadí odebírání vrcholů si tedy můžeme rozložit na dvě nezávislé části: Nejprve si pro každé i=1,…, n vybereme, ze kterého podstromu budeme odebírat i-tý vrchol. Poté pro každý podstrom zvlášť určíme, v jakém pořadí odebereme jeho vrcholy.
Pro první část musíme zjistit počet všech různých posloupností čísel od 1 do k takových, že každé číslo i\in\{1,…, k\} se v posloupnosti vyskytuje ni-krát. Nejprve si tedy z n možných pozic vybereme n1 těch, na které dáme číslo 1 (to lze {n\choose n1} způsoby). Ze zbývajících n-n1 pozic vybereme n2 těch, na které dáme číslo 2 (to lze C(n-n1, n2 způsoby, kde C(n, k) označuje kombinační číslo n nad k). A tak dále. Celkem je tedy počet takových posloupností C(n, n1) C(n-n1, n2) … C(n-…, nk) = n! / (n1! n2! … nk!).
Pro druhou část potřebujeme pro každý podstrom určit počet pořadí odebrání jeho vrcholů. Tato pořadí jsou ale právě hodnoty pv(u1), …, pv(uk), které získáme z rekurze. Protože všechny volby jsou na sobě nezávislé, počet všech možností získáme jejich pronásobením a pv(u) = (n! pv(u1) … pv(uk)) / (n1! … nk!). Nakonec takto spočítáme i pv(v). Uvedená rekurze navštíví každý vrchol právě jednou, a proto celý výpočet pv(v) zabere linearní čas.
Protože musíme určit pv(v) pro každý vrchol v, celý algoritmus běží v Ο(N^2). Jak to zrychlit? Zafixujeme si až do konce výpočtu jediný pevný kořen v a spustíme na něj výše uvedený algoritmus, takže spočítáme pv(u) pro každý vrchol u.
Máme spočten počet pořadí končících vrcholem v. My bychom nyní potřebovali zahrnout případy, kdy končíme vrcholem jiným. Budeme postupovat induktivně po hladinách stromu. První hladina je vyřešená, na ní je pouze vrchol v. Předpokládejme, že máme spočítán kompletní výsledek pro všechny vrcholy v k-té hladině a vezměme vrchol u z (k+1)-ní hladiny. Nyní prohlásíme u za kořen stromu. Co se změní?
Původní synové u zůstali, kde byli, a pro ně máme spočteno pv(ui) = pu(ui). Zároveň vrcholu u přibyl jediný další syn, jeho bývalý otec w, který byl z k-té hladiny, takže pro něj již máme spočten celkový počet pořadí končících w, tedy pw(w). Abychom mohli spočítat pu(u), potřebujeme už jen spočítat pu(w). Všimněme si, že pu(w) získáme tak, že při výpočtu pw(w) ignorujeme podstrom pod u. Označíme-li nu počet vrcholů v podstromě s kořenem u při zakořenění ve w, dostáváme pu(w) = pw(w) ((N-1-nu)! nu!) / ((N-1)! pw(u)) a pu(u) už nyní dopočítáme jako v předchozím postupu.
V první fázi tohoto řešení jsme spočítali pv(u) pro pevné v a všechny vrcholy, to zabralo Ο(N). V druhé fázi jsme prošli strom po hladinách a provedli konstantně mnoho výpočtů v každém vrcholu, takže tato fáze také zabrala Ο(N), čímž jsme získali lineární řešení.
Povšimněme si, že vrátí-li bojí_se(a, b) hodnotu 0, pak čert b není vhodný kandidát na ďábla. Naopak, vrátí-li hodnotu 1, pak čert a není vhodný kandidát na ďábla. Budeme si udržovat seznam S čertů, o kterých jsme ještě neukázali, že se nehodí na ďábla. Dokud S obsahuje alespoň dva čerty, dva z nich (a a b) si vybereme a položíme dotaz bojí_se(a, b). Tím právě jednoho z nich vyřadíme ze seznamu. Po N-1 opakováních bude S obsahovat právě jednoho čerta c, jediného možného kandidáta na ďábla.
Zbývá nám ale ještě ověřit, zda se čerta c všichni bojí a on se nikoho nebojí. To zvládneme dalšími 2(N-1) dotazy, celkový počet dotazů je tedy 3N-3. Tento postup lze ale ještě vylepšit: je zbytečné se v druhé části dávat dotazy, které jsme už položili v první části. Označme si jako p(x) počet dotazů na čerta x v první části. Celkový počet dotazů bude 3N-3-p(c).
Potřebujeme tedy první část dotazů rozvrhnout tak, aby p(c) bylo co největší možné. Vhodný způsob, jak toho dosáhnout, je vždy porovnávat čerty v S, na než jsme zatím kladli nejméně dotazů (takže nám nehrozí, že bychom z S vyřadili čerta s mnoha dotazy). Pro jednoduchost uvažme případ, že N=2k pro nějaké přirozené číslo k. Pak v prvních N/2 dotazech porovnáváme čerty, na které jsme se ještě neptali. V dalších N/4 dotazech porovnáváme čerty, na které jsme se ptali jednou. V dalších N/8 dotazech porovnáváme čerty, na které jsme se ptali dvakrát. A tak dále, až v posledním 1=N/2k dotazu porovnáváme čerty, na které jsme se ptali (k-1)-krát. Na konci tedy bude p(c)=k=log2 N.
V obecnosti obdobně nahlédneme, že p(c) ≥ ⌊ log2 N ⌋. Celkový počet dotazů tedy bude nejvýše 3N-3- ⌊ log2 N ⌋. O trochu složitější úvahou je možné ukázat, že tento počet je optimální a žádný lepší algoritmus neexistuje.
Nejprve si rozmysleme, jak bychom úlohu řešili, kdyby všechny ulice byly jednosměrné. Aby úloha měla řešení, je samozřejmě nutné, aby síť ulic byla souvislá. Dále je nutné, aby z každé křižovatky ven vycházelo stejně ulic, jako do ní vchází. Ukažme si, že za těchto podmínek řešení vždy existuje.
Vyražme z křižovatky číslo 1 a vždy jděme libovolnou ještě nepoužitou ulicí v povoleném směru, dokud je to možné. Kde taková procházka skončí? Když přijdeme na křižovatku k různou od křižovatky 1, pak jsme do křižovatky k vstoupili o jedna vícekrát, než kolikrát jsme z ní odešli. Ale z každé křižovatky vede ven stejně ulic jako dovnitř, takže jistě máme kudy odejít. Proto prochazka musí skončit na křižovatce 1. Uvažujme nějakou takovou procházku P=1, k1, k2, …, kt, 1. Jestliže jsme v ní neprošli všechny ulice, pak díky souvislosti sítě existuje nějaká křižovatka ki v procházce, z níž vede ještě nepoužitá ulice. Nalezenou procházku tedy můžeme prodloužit: nejprve projdeme začátek 1, k1, …, ki procházky P. Dále z ki vyrazíme ulicí nepoužitou v P a dokud je to možné, jdeme v povoleném směru libovolnou ještě nepoužitou ulicí, která se nevyskytuje v procházce P. Snadno nahlédneme, že skončíme opět na křižovatce ki. Z ní pak pokračujeme dle zbytku procházky P, tedy ki, ki+1, …, kt, 1.
Tento postup opakujeme a procházku prodlužujeme, dokud se v ní nevyskytují všechny ulice. Popsaný algoritmus lze implementovat v lineárním čase: Při prvním průchodu si čísla křižovatek ukládáme na zásobník. Poté je odebíráme a vypisujeme od konce, dokud nedojdeme ke křižovatce ki, z níž vede ještě nepoužitá ulice. Z ní opět procházíme a přidáváme křižovatky na zásobník. Toto opakujeme, dokud se zásobník nevyprázdní. Takto jsme nalezli procházku, která používá každou ulici právě jednou, ale vypsali jsme ji v opačném pořadí. To můžeme opravit ukládáním do pomocného seznamu, který nakonec otočíme, nebo přímo drobným trikem: ulice povolíme procházet pouze v protisměru.
Zbývá dořešit obousměrně použitelné ulice. Zjevně je třeba ulice zjednosměrnit tak, aby do každé křižovatky vcházel stejný počet ulic, jako z ní vychází. Nejprve proveďme několik jednoduchých pozorování. Jestliže se na nějaké křižovatce sejde lichý počet ulic, úloha nemá řešení. Stejně tak řešení neexistuje, jestliže je pro nějakou křižovatku k rozdíl mezi počtem vcházejících a vycházejících ulic větší, než počet obousměrných ulic sousedících s k. Je-li tento rozdíl přesně roven počtu obousměrných ulic sousedících s k, pak tyto obousměrné ulice musíme naorientovat všechny stejným směrem tak, aby do křižovatky k vcházel stejný počet ulic, jako z ní vychází. Povšimněme si, že jedna z popsaných situací nutně nastane u každé křižovatky, s níž sousedí právě jedna obousměrná ulice. Takto postupně orientujeme ulice, pro něž je směr vynucen. Každou křižovatku stačí kontrolovat nejvýše tolikrát, kolikrát se u ní naorientuje nějaká ulice, tuto část algoritmu lze tedy realizovat v lineárním čase.
Předpokládejme nyní, že žádná z výše popsaných situací již nenastává. Pak s každou křižovatkou sousedí buď žádná, nebo dvě obousměrné ulice, a počet jednosměrných vcházejících ulic je stejný jako počet vycházejících. Obousměrné ulice tedy tvoří několik cyklů, v nichž můžeme orientaci zvolit libovolně, ale stejně pro všechny ulice v cyklu.
Dohromady lze celý algoritmus implementovat s lineární časovou i paměťovou složitostí.
Úloha 1: Uvažme libovolnou síť, skládající se pouze z omezení XOR. Přiřadíme-li každé proměnné hodnotu 1, pak všechna omezení jsou splněna. Ale XOR4(w,x,y,z) nepřijímá ohodnocení w=x=y=z=1. Proto žádná síť, která se skládá pouze z omezení XOR, nesimuluje XOR4.
Úloha 2: Příkladem takové sítě je XOR(w,x,a), XOR(a,y,b), XOR(z,b,c), ZERO(c). Proměnná c má hodnotu 0, díky omezení XOR(z,b,c) má tedy proměnná b opačnou hodnotu než z. První dvě omezení jsou splnitelná (vhodnou volbou hodnoty proměnné a) právě tehdy, má-li z proměnných w, x, y a b sudý počet hodnotu 1. Dohromady lze tedy všechna omezení splnit právě tehdy, má-li z proměnných w, x, y a z lichý počet hodnotu 1.
Úloha 3: Síť XOR4 odmítá právě ta ohodnocení, v nichž se vyskytují 0, 2 nebo 4 jedničky. Nejprve si ukažme, jak pomocí NAE zakázat ohodnocení, v nichž se vyskytují právě 2 jedničky. Uvažme síť NAE(w,x,a), NAE(y,z,a) se vstupními proměnnými w, x, y a z. Ta vstup přijímá, jestliže první a druhé omezení nevynucují opačná ohodnocení pro proměnnou a. Síť tedy odmítá právě ohodnocení taková, že w=x=1 a y=z=0, nebo w=x=0 a y=z=1. Obdobně prohozením proměnných x, y a z získáme sítě zakazující ohodnocení w=y=1 a x=z=0, nebo w=y=0 a y=x=1, případně w=z=1 a x=y=0, nebo w=z=0 a x=y=1.
Ještě potřebujeme zakázat ohodnocení w=x=y=z=0 a w=x=y=z=1. To dělá síť NAE(w,x,d), NAE(y,z,e), NAE(d,d,e). Síť XOR4(w,x,y,z) je tedy simulována sítí NAE(w,x,a), NAE(y,z,a), NAE(w,y,b), NAE(x,z,b), NAE(w,z,c), NAE(x,y,c), NAE(w,x,d), NAE(y,z,e), NAE(d,d,e). \cr }}