Przeszukiwanie w głąb (DFS)

DFS - ang. Depth-First Search przeszukiwanie w głąb, jest chyba najprostszym algorytmem grafowym, a wygląda on tak:

void DFS(int v)
{
    if (odwiedzony[v]) return;
    odwiedzony[v]=1;
    wywolal_DFS_dla_wszystkich_sasiadow_v();
}

I w ten sposobik przejdziemy sobie cały graf ;) a wywołanie dla sąsiadów wygląda zwykle tak:

void sasiedzi()
{
    for (int i=0; i<G[v]; i++)
        DFS(G[v][i]);
}

Ale DFS można "ulepszyć", przez co będzie nam znajdować cykle w grafie.

int odwiedzony[N]; //int, nie bool!! widać że Ci nie żal pamięci - char wystarczy...
 
void DFS(int v)
{
    if (odwiedzony[v]==2) return;
    if (odwiedzony[v]==1) znalezlismy_cykl_i_tylko_od_nas_zalezy_co_z_tym_zrobic;
    odwiedzony[v]=1;
    wywolal_DFS_dla_wszystkich_sasiadow_v();
    odwiedzony[v]=2;
}

OK, ale czemu to działa?? Jak wejdziemy do jakiegoś wierzchołka, to damy mu cyfre "1", teraz idziemy sobie dalej, jak kiedyś do niego wrócimy, no to zrobiliśmy cykl, a wierzchołek będzie miał jedynke tylko podczas zwiedzania wierzchołków, do których doszliśmy idąc przez niego, jak już wszystkie takowe odwiedzimy, to zmieni się mu cyfra na dwójkę.