Ktoś podpowie jak zrobić TRZ szybciej niż O(n^2)?

Niezbyt szczegółowy opis naszego rozwiązania, mamy nadzieję, że jak chcesz zrozumieć to zrozumiesz.

Po pierwsze dla każdego cyklu bazowego losujemy 60-bitową wartość i dla każdej krawędzi spamiętujemy xora wartości cykli bazowych, które przez nią przechodzą. Dla krawędzi taką liczbę możemy nazywać jej haszem. Zbiór krawędzi rozspójnia graf, jeśli hasze jakiegoś jego niepustego podzbioru xorują się do zera. Mamy kilka prostych przypadków: krawędź o wartości 0 (most); dwie krawędzie o tej samej wartości. Możemy łatwo w czasie liniowym policzyć wszystkie trójki krawędzi, które zawierają jeden z tych przypadków. Następnie dla każdego mostu możemy scalić oba jego końce. To samo, gdy mamy wiele krawędzi o tej samej wartości: dla wszystkich nich oprócz jednej (dowolnej) scalamy ich końce. Pozbywamy się też również powstałych pętli, nie są one w niczym przydatne. W ten sposób otrzymujemy trzyspójny graf nie zmieniając zbioru trójek haszy xorujących się do zera. Nie musimy się teraz skupiać na dokładnym policzeniu wyniku, ale na znalezieniu wszystkich trójek haszy, które xorują się do zera. Być może niektóre z nich znajdziemy wiele razy, nie szkodzi, na koniec wyciągniemy z tego wynik.

Mając trzyspójny graf znajdźmy dowolne jego drzewo dfs i rozważmy możliwe przypadki trójek krawędzi: 3 niedrzewowe, 2 niedrzewowe i 1 drzewowa, 1 niedrzewowa i 2 drzewowe, 3 drzewowe.

Pierwszy przypadek jest niemożliwy, gdyż usuwając jedynie niedrzewowe krawędzie nie rozspójnimy grafu.

Drugi jest prosty: niezależnie od tego jak wyznaczaliśmy cykle bazowe, to dla dowolnego drzewa rozpinającego możemy myśleć, że to jego krawędzie niedrzewowe wyznaczały owe cykle. Przez szukaną krawędź drzewową muszą zatem przechodzić dokładnie dwie krawędzie niedrzewowe. Możemy się przeiterować po krawędzi drzewowej i jeśli ona bierze udział w tym przypadku, to inną krawędzią w takiej trójce musi być dowolna krawędź niedrzewowa przechodząca nad nią.

Trzeci przypadek jest nieco trudniejszy, ale nadal możliwy do rozwiązania. Dwie krawędzie drzewowe muszą leżeć jedna nad drugą i zbiór krawędzi niedrzewowych przechodzących przez nie musi różnić się dokładnie jedną krawędzią. Mamy tu dwa podprzypadki: większy zbiór jest niżej lub wyżej. W obu przypadkach istnieje jeden kandydat na krawędź niedrzewową, która nie przechodzi nad tą drugą krawędzią drzewową. Możemy to rozwiązać standardowymi drzewowymi operacjami, np. zamiatając krawędzie niedrzewowe w odpowiedniej kolejności (zależnie od podprzypadku) i używając find&union. Można to też zrobić liniowo, ale jest to trochę trudniejsze.

Czwarty przypadek jest najtrudniejszy i ma dwa podprzypadki. Albo trzy krawędzie leżą po kolei jedna pod drugą, albo istnieje wierzchołek, który w dwóch poddrzewach ma dwie krawędzie, a nad sobą jedną. Ten drugi podprzypadek nadal da się rozwiązać, jednak pierwszego nie umiemy, dlatego nie rozwiążemy żadnego z nich.

Znaleźliśmy zatem wszystkie trójki haszy takie, że chociaż jedna krawędź w takiej trójce jest niedrzewowa. Przypomnijmy sobie zatem, że nasz graf był trzyspójny. Na pewno zachodzi zatem m>=1.5n (stopnie muszą wynosić co najmniej 3). Dla każdej krawędzi niedrzewowej scalmy zatem oba jej końce, otrzymując w ten sposób nowy graf (znowu pozbywając się pętli). Pozbędziemy się w tej sposób co najmniej m-(n-1) krawędzi, zatem co najmniej 1/3 z nich. Nowy graf nadal musi być trzyspójny, czyli nadal musi spełniać wspomnianą nierówność. Czy jeśli istniała trójka krawędzi drzewowych, których wartości xorowały się do zera, to czy mogła ona w ten sposób zniknąć? Nie, jeśli była ona poprawnym cięciem grafu, to na pewno dla żadnej z tych krawędzi nie scaliliśmy obu jej końców. Możemy zatem ponownie przejrzeć wszystkie przypadki i znowu redukować nasz graf. Całość powtarzamy, aż w grafie zostanie jeden wierzchołek.

Możemy zatem szybko (w czasie O(mlog(m)), O(mlog*(m)) lub nawet O(m)) znaleźć wszystkie trójki, które nas interesują, a następnie zredukować nasz graf, którego rozmiar maleje geometrycznie. Sumaryczna złożoność będzie zatem taka, jak złożoność jednej fazy.

Na koniec, mając wszystkie pożądane trójki i dla każdego hasza wiedząc, ile krawędzi w pierwotnym grafie go miało, możemy łatwo policzyć wynik.

Nice - miałem ten sam podział na przypadki, ale nie scalałem krawędzi, i również zaciąłem się na podprzypadku 4.1 :-) Jakoś nawet w niektórych przypadkach czasem odejmowałem coś co policzyłem za dużo w innych, że w końcu liczyło to każdą konfigurację raz, no ale 4.1 wciąż miałem kwadratowo.

To rozumiem że z waszego rozwiązania wynika, że jeśli weźmiemy zbiór hashy dla krawędzi w grafie to liczba trójek xorujących się do 0 jest liniowa? Nie widzę czemu miałaby to być prawda dla dowolnego zbioru hashy, więc rozumiem że jest to własność wynikająca z tego jak ten zbiór powstał?

Zgadza się. Oczywiście nadal mogą zachodzić problemy probabilistyczne wynikające z liczby wylosowanych bitów, ale taki jest zamysł.

Ja spróbuję opisać swój pomysł na deterministyczny algorytm, którego nie próbowałem implementować.
Bazowane na 2 prackach. Jedna bardziej standardowa, która wyznacza 3-edge spójne składowe w grafie, np. https://sci-hub.se/10.1016/j.ipl.2013.09.010 3-edge spójne składowe to podział wierzchołków na grupki taki, że pomiędzy dwoma wierzchołkami jest flow >=3 iff są w tej samej grupce. Zauważę, że wbrew nazwie, takie grupki nie muszą być spójne.
Druga robiące prawie że to samo zadanie co to to Optimal Offline Dynamic 2,3-Edge/Vertex Connectivity https://arxiv.org/abs/1708.03812
W tej drugiej jest de facto opisany m.in. sposób na odpowiadanie offline czy dwa dane wierzchołki są w tej samej 3-edge spójnej składowej w dynamicznym grafie, do którego wchodzą i wychodzą krawędzie i wystarczy tego algosa lekko dostosować. Stosujemy tę metodologię, gdzie modelujemy ten dynamiczny graf tak aby i-ta krawędź żyła w każdym momencie poza i-tym, tzn. na prefiksie [1, i-1] oraz sufiksie [i+1, m]. To co tam się dzieje to taki mniej więcej tak rozbijanie przedziału życia krawędzi na przedziały bazowe albo też można inaczej o tym myśleć jak o plecaku bez jednego. Jak schodzimy w głąb drzewa przedziałowego, to mamy część krawędzi już scomittowanych, a część, która gdzieś się jeszcze pojawi niżej i zbiór końców takich krawędzi nazwijmy aktywnym zbiorem W. Chcemy nasz duży graf G zastąpić mniejszym H, który będzie równoważny pod względem 3-edge spójności na aktywnym zbiorze W, tzn. dla każdej pary wierzchołków u,v \in W zachodzi że min(flow_G(u, v), 3) = min(flow_H(u, v), 3). Na początek wyznaczamy w nim liniowo te 3-spójne składowe i każdą z nich ściągamy do 1 wierzchołka (nie jest to ściągnięcie w standardowym sensie, bo taki zbiór nie musi być spójny, ale wiadomo). To co zostanie to graf, gdzie nie ma pary wierzchołków o flow>=3. Takie grafy to kaktusy, gdzie każda krawędź leży na max 1 cyklu (wierzchołki mogą). Niestety taki kaktus wciąż może być duży w porównaniu do rozmiaru W, a chcielibyśmy aby jego rozmiar był liniowy względem W. Na szczęście standardowo można pościągać wszelkie długie ścieżki pamiętając o tym aby aktualizować odpowiedź i jak ściągamy ścieżkę to trzeba też pamiętać jej długość, zatem mamy krawędzie z krotnościami. Odcinamy też "liście" kaktusa, w których nie ma już aktywnych wierzchołków, tzn. takie "liściowe cykle", na których nie ma nic z W. Łatwo zauważyć, że po wykonaniu takich operacji nasz kaktus skurczy się do rozmiaru liniowego od W, zatem operując na przedziale o długości k mamy preserver 3-spójności o rozmiarze liniowym od k i wszystko śmiga. Złożoność jakiś O(n polylog(n)), być może jak się uważnie zaimplementuje to nawet się da O(n log n).