int main() { scanf("%d", &n); for(int i = 0; i < n-1; ++i) { scanf("%d %d", &from, &to); V[from].push_back(to); V[to].push_back(from);
for(int i = 0; i <= n; i++) { pre[i]=0; treeSize[i]=0; vis[i]=false;
for(int i = 0; i < LOGN; i++) for(int j = 0; j < MAX; j++) P[i][j]=0;
vis=true; dfs(1);
P=1; for(int i = 1; i < LOGN; i++) for(int j = 1; j < MAX; j++) P[i][j]=P[i-1][P[i-1][j]]; printf("%d\n",lca(1, 4)); printf("%d\n",lca(3, 5)); return 0; }
Powyższy algorytm ma złożoność obliczeniową rzędu – gdzie to ilość wierzchołków w drzewie, a to ilość zapytań o najniższego wspólnego przodka. Innym sposobem obliczania dla dwóch wierzchołków drzewa ich najniższego wspólnego przodka jest algorytm Tarjana. Istnieje także algorytm opublikowany w 2000 roku o złożoności obliczeniowej
Bibliografia https://oi.edu.pl/static/attachment/20110811/oi9.pdf.
Kategoria:Teoria grafów