497. Trójkąty Jednobarwne [TROJEDNO]

Zadanie:
https://pl.spoj.com/problems/TROJEDNO

Skrócony opis problemu:

Mając dane $n$ będące stopniem grafu pełnego oraz $m$ czerwonych krawędzi tego grafu (pozostałe $\frac{n(n-1)}{2}-m$ krawędzi jest czarna) oblicz ilość jednobarwnych trójkątów w tym grafie. Jednobarwny trójkąt, to taka trójka wierzchołków, że wszystkie 3 krawędzie między nimi są jednego koloru.

Np. dla $n=6, m=9$ i tych czerwonych krawędzi: 1-2, 2-3, 3-4, 4-5, 5-6, 6-1, 1-4, 2-5, 3-6 wynik to 2. Graf ten bowiem wygląda następująco:

Jak widzimy, są 2 trójkąty jednobarwne: 1-3-5 oraz 2-4-6.



Rozwiązanie naiwne:

Możemy sprawdzić każdą trójkę wierzchołków w grafie i jeśli między wszystkimi będzie czerwona krawędź lub jej nie będzie to inkrementujemy wynik, który po przejściu wszystkich trójek wypisujemy.

Złożoność: $O(n^3)$, jako że trójek w grafie pełnym jest $\frac{n(n-1)(n-2)}{6}$.

Rozwiązanie sprytne:

Rozwiązanie opisane na podstawie informacji ze strony Olimpiady Informatycznej.

Możemy zredukować ten problem do znalezienie ilości trójkątów różnobarwnych. Mianowicie wiemy, ile jest trójkątów (trójek wierzchołków) w grafie i jeśli będziemy wiedzieli, ile jest trójkątów różnobarwnych, to po odjęciu drugiego od pierwszego otrzymamy ilość trójkątów jednobarwnych.

Czy łatwiej jest zliczyć trójkąty różnobarwne? Otóż tak. Musimy zauważyć pewną właściwość trójkąta różnobarwnego. Każdy taki trójkąt ma dokładnie 2 wierzchołki, w których spotykają się 2 różnokolorowe krawędzie. Co więcej, dla każdej takiej pary różnobarwnych krawędzi wychodzących z danego wierzchołka mamy trójkąt różnobarwny. Dlaczego? Bo niezależnie od koloru trzeciej krawędzi i tak będzie się on składał z 2 kolorów. Przypominam, że trzecia krawędź musi istnieć, gdyż mamy graf pełny.

Dla każdego wierzchołka wyznaczamy zatem ile ma krawędzi czerwonych (np. przy pobieraniu zwiększamy "stopień czerwoności" wierzchołka). Ilość czarnych krawędzi danego wierzchołka przy $x$ czerwonych krawędziach równa jest $n-1-x$. Czemu? Gdyż mamy graf pełny, więc każdy z wierzchołków ma $n-1$ krawędzi (łączy się z wszystkimi oprócz sobą), a mamy tylko 2 rodzaje krawędzi, więc odejmujemy od sumarycznej ilości krawędzi danego wierzchołka ilość jego czerwonych krawędzi.

Kiedy już mamy dla wierzchołka $A$ ilość jego czerwonych i czarnych krawędzi, obliczamy w czasie stałym ilość trójkątów różnobarwnych, przez niego przechodzących. Jak? Zliczamy pary krawędzi różnobarwnych. Jest ich $x(n-1-x)$, bo łączymy w parę każdą czerwoną krawędź z każdą czarną.

Na koniec wystarczy zsumować ilości trójkątów różnobarwnych dla każdego wierzchołka i... podzielić wynik przez 2. Ale ale czemu przez 2, a nie przez 3‽ Przecież trójkąt ma 3 wierzchołki, więc każdy trójkąt zostanie zliczony 3 razy! Otóż nie - każdy zostanie zliczony 2 razy, gdyż w trójkącie różnobarwnym jeden wierzchołek musi łączyć 2 krawędzie o tym samym kolorze. Wynik końcowy to zatem:

$$\binom{n}{3} - \frac{1}{2} \sum_{i=1}^n x_i(n-1-x_i)$$

Złożoność: $O(n+m)$, gdyż dla każdego wierzchołka zliczamy jego czerwone krawędzie w czasie $O(m)$ przy wczytywaniu, a potem dla każdego z $n$ wierzchołków dodajemy ilość jego trójkątów równoważnych do wyniku.

Ostateczny algorytm:

int main()
{
    int n, m, a, b, i;
    int red[n+1]; // "stopnie czerwoności" wierzchołków; na początku tablica wyzerowana

    get(n, m);
    while(m--)
        get(a, b),
        ++red[a],
        ++red[b];
    for(m = 0, i = 1; i <= n; ++i) // zmiennej m już nie potrzebujemy, więc będziemy w niej trzymać nasz wynik
        m += red[i]*(n-1-red[i]);
    print(n*(n-1)*(n-2)/6-m/2);
}