W programowaniu sportowym ogromne znaczenie ma szybkość i wygoda implementacji. W szczególności istotne jest, żeby często występujące konstrukcje pisać efektywnie i bez błędów. W serii wpisów Porady klepaka skupię się na sztuczkach i poradach dotyczących sprawnego kodowania.

W tym wpisie chciałbym podzielić się z Wami sztuczkę użyteczną w zadaniach, w której należy napisać wiele algorytmów przeszukiwania grafu w głąb. Takie sytuacje nierzadko pojawiają się przy okazji bardziej skomplikowanych zadań na drzewach.

Przedstawienie problemu

Przykładowo, powiedzmy, że pierwszym DFS naszego algorytmu ma służyć do policzenia rozmiaru poddrzew oraz kolejności preorder, zanim będziemy mogli wykonać kolejne przeszukiwanie w głąb. Kod mógłby wyglądać wtedy następująco:

#define pb push_back

const int N = 200003;
vector<int> G[N];     /* Graf reprezentowany jako listy sąsiedztwa */
bool vis[N];          /* Tablica odwiedzonych wierzchołków */
int sz[N], pre[N];    /* Tablice rozmiaru poddrzewa oraz czasu wejścia */
int tim = 0;          /* Licznik czasu wejścia */

void dfs1(int v) {
    vis[v] = true;
    sz[v] = 1;
    pre[v] = tim++;   /*  Najpierw przypisz aktualną wartość tim,
                         a potem zwiększymy wartość licznika       */
    for (auto u: G[v]) {
        if (!vis[u]) {
            dfs1(u);
            sz[v] += sz[u];
        }
    }
}

void dfs2(int v) {
    ... /* Drugi dfs, który korzysta z policzonych tablic sz oraz pre */
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].pb(v);
        G[v].pb(u);
    }
    dfs1(1);
    /* Czyścimy tablicę odwiedzonych przed następnym
       przeszukiwaniem w głąb */
    fill(vis + 1, vis + n + 1, false);
    dfs2(1);
}

Z tym kodem pozornie nie ma nic złego – jest elegancki i czytelny, robi co należy. Jednakże, jest w nim kilka momentów, które mają potencjał do wprowadzenia subtelnych, irytujących do odnalezienia błędów.

  1. Tablica odwiedzonych wierzchołków – kiedy wielokrotnie chcemy przeszukać graf, tablica vis musi zostać wyczyszczona. Co, jeśli przypadkiem zapomnimy to zrobić?
  2. Tablice numerujemy od 0, a wierzchołki od 1 – W takim razie czyszcząc tablicę vis musimy pamiętać, że ostatni element również znajduje się pod indeksem n, a nie n - 1.
  3. Za każdym razem pisząc DFS musimy pamiętać o sprawdzaniu, czy dany wierzchołek nie był już odwiedzony. Jeśli warunek wejścia do danego wierzchołka staje się bardziej skomplikowany, to kolejne miejsce, w którym możemy popełnić błąd.

W każdym z wymienionych przeze mnie punktów pojawia się problem z tablicą vis. Pewnym rozwiązaniem tego problemu, jak pewnie wiele z Was wie, jest wprowadzenie dodatkowego argumentu rodzica do funkcji dfs. To jednak nie rozwiązuje problemu z punktu 3. oraz jest dodatkowym kawałkiem kodu, który trzeba dopisać (i w ciele funkcji i przy jej wywołaniach).

Ktoś mógłby powiedzieć, że przesadzam i że żaden z wymienionych punktów nie jest żadną przeszkodą dla doświadczonego zawodnika. To pewnie prawda, ale chyba nie ma nikogo, komu nie zdarzyło się wprowadzić banalnego buga, który wymagał trochę czasu na odnalezienie. Z tego powodu warto pisać kod tak, żeby minimalizować ‘‘buggogenne’’ elementy.

Nawet, jeśli żaden z powyższych punktów do Ciebie nie przemawia, to i tak trick, który chcę zaprezentować, może Ci się spodobać.

Trick

Skoro każdy z naszych DFSów ma wyglądać tak, że nie chcemy odwiedzać rodzica aktualnie odwiedzanego wierzchołka v, to może po prostu… usuńmy go z listy sąsiedztwa v! Brzmi absurdalnie?

void dfs(int v) {
    for (auto u: G[v]) {
        /* Znajdźmy v w liście sąsiedztwa u */
        auto it = find(G[u].begin(), G[u].end(), v);
        /* Usuńmy v z tej listy sąsiedztwa */
        G[u].erase(it);
        dfs(u);
    }
}

Oczywiście kod można skrócić jeszcze bardziej i wywołanie funkcji find możemy napisać od razu wywołując erase, np. tak G[u].erase(find(all(G[u]), v)) (o ile zdefiniujemy sobie #define all(x) (x).begin(), (x).end()).

Od tego momentu nasze drzewo staje się skierowane, a krawędzie idą jedynie z rodziców to dzieci i nigdy odwrotnie. To powoduje, że tablica odwiedzonych wierzchołków już w ogóle nie jest potrzebna!

Czy to działa szybko?

Nie tylko dla mnie, ale dla innych osób ten trick początkowo wydawał się dosyć zaskakujący, szczególnie z powodu rzadko używanego erase na vectorze, które jak wiadomo działa w czasie liniowym względem rozmiaru vectora. Jednakże, dla każdego wierzchołka płacimy kosztem liniowym względem liczby jego sąsiadów, bo operację wykonujemy dokładnie raz – zaraz przed wejściem do tego wierzchołka. Zatem całkowity, dodatkowy czas działania tej operacji, jest liniowy względem rozmiaru grafu.

Podsumowanie

Moim zdaniem trick jest bardzo elegancki, przyspiesza implementację oraz odbiera potencjalne wektory popełnienia nieprzyjemnych błędów implementacyjnych. Pisząc następne zadanie na drzewach, czemu nie spróbować z niego skorzystać?

Należy jednak pamiętać, że trick ma sens tylko w zadaniach, w których korzeń drzewa się nie zmienia, zatem może nie być zbyt przydatny np. w zadaniach z drzewem centroidów.