// DFS -- predrátame si hĺbku

void dfs(v){
    hlbka[v] = hlbka[otec(v)]+1;
    for (int i=0; i<synovia[v]; i++)
        dfs(synovia[v][i]);
}

// ideme hore kým sa nestretnú
// O<1,n>
if(hlbka[x]>hlbka[y]) swap(x,y)
while (hlbka[x]<hlbka[y]) x=otec[x];
while (x!=y){x=otec[x]; y=otec[y]}
return x;

// O<n, sqrt(n)>
// nr = velkost bloku -- sqrt(n)
void dfs(v){
    if (hlbka[v] < nr)
        skok[v] = 0;
    else
        if(hlbka[v] % nr == 0)
            skok[v] = otec[v];
    else
    skok[v] = skok[ otec[v] ]; 

    for (int i=0; i<synovia[v]; i++)
        dfs(synovia[v][i]);
}

// Odpoveď
while (skok[x] != skok[y])
    if (hlbka[x] > hlbka[y])
        x = skok[x];
    else
        y = skok[y]; 

// rôzne skoky
// skoky[N][log(N)]
// skoky[i][j] = -1; 
// O<nlogn, logn>

// prvy predok je otec
for (int i = 0; i < n; i++)
    skoky[i][0] = otec[i];

for (int j = 1; 1 << j < n; j++) //každá úroveň
    for (int i = 0; i < n; i++)  
        if (skoky[i][j-1] != -1)
            skoky[i][j] = skoky[ skoky[i][j-1] ][j-1];


// odpoveď na otázku p,q        

if (hlbka[p] < hlbka[q]) swap(p,q);

//p vyskáče na úroveň q
for (i = log(hlbka[p]); i >= 0; i--)
    if (hlbka[p] - (1 << i) >= hlbka[q])
        p = skoky[p][i]; 

if (p == q)
    return p; 

for (i = log(hlbka[p]); i >= 0; i--)
    if (skoky[p][i] != -1 && skoky[p][i] != skoky[q][i])
        p = skoky[p][i], q = skoky[q][i]; 

return otec[p];

Čas poslednej úpravy: 11. júl 2018 10:53