Cel mai apropiat strămoș comun: vector de tați C++

Într-un arbore cu rădăcină, un strămoș al unui vârf se află pe drumul de la rădăcină la acel vârf. În această lecție includem și vârful însuși. Cel mai apropiat strămoș comun al lui u și v este strămoșul lor comun aflat cel mai departe de rădăcină.

Un contract care permite niveluri la citire

Citim 1≤n≤1000. Rădăcina este vârful 1. Pentru fiecare i de la 2 la n citim tatăl, cu restricția 1≤tata[i]<i. Apoi citim u și v, între 1 și n. Afișăm strămoșul comun cel mai apropiat.

Restricția tata[i]<i este importantă: nivelul tatălui este deja calculat când îl citim pe i. Nivelul rădăcinii este zero, iar nivel[i]=nivel[tata[i]]+1. Pentru o numerotare arbitrară ar trebui calculat nivelul printr-o parcurgere sau altă procedură, nu prin această singură buclă.

Aducem vârfurile pe același nivel

Dacă u este mai adânc, îl înlocuim repetat cu tatăl lui până ajunge la nivelul lui v. Facem simetric pentru v. Un strămoș comun nu poate fi sub vârful mai puțin adânc, deci aceste urcări nu sar peste răspuns.

După egalizare, dacă vârfurile coincid, am găsit răspunsul. Altfel le urcăm simultan câte o muchie. Prima întâlnire este strămoșul comun cel mai adânc: toate nivelurile mai mari au fost verificate fără egalitate.

În arborele cu părinți 2→1,3→1,4→2,5→2,6→4, strămoșul comun cel mai apropiat al lui 6 și 5 este 2. Urcăm 6 la 4, apoi 4 și 5 la 2.Mărește schema ↗

Varianta cu tablou clasic

#include <iostream>
using namespace std;
int main() {
    int n; cin >> n; int tata[1001]={},nivel[1001]={};
    for(int i=2;i<=n;++i) { cin >> tata[i]; nivel[i]=nivel[tata[i]]+1; }
    int u,v; cin >> u >> v;
    while(nivel[u]>nivel[v]) u=tata[u];
    while(nivel[v]>nivel[u]) v=tata[v];
    while(u!=v) { u=tata[u]; v=tata[v]; }
    cout << u << '\n';
}

Varianta echivalentă cu std::vector

Păstrăm limitele intrării și aceleași rezultate. Tabloul clasic rezervă capacitatea maximă; vectorul construiește numărul de elemente necesare. Indicii folosiți de algoritm rămân aceiași.

#include <vector>

#include <iostream>
using namespace std;
int main() {
    int n; cin >> n; vector<int> tata(n+1),nivel(n+1);
    for(int i=2;i<=n;++i) { cin >> tata[i]; nivel[i]=nivel[tata[i]]+1; }
    int u,v; cin >> u >> v;
    while(nivel[u]>nivel[v]) u=tata[u];
    while(nivel[v]>nivel[u]) v=tata[v];
    while(u!=v) { u=tata[u]; v=tata[v]; }
    cout << u << '\n';
}

Exemplu cu adâncimi diferite

Consideră tații pentru vârfurile 2..6: 1 1 2 2 4. Vârful 6 este copilul lui 4, iar 4 și 5 sunt copii ai lui 2. Pentru u=6 și v=5, urcăm mai întâi 6 la 4, egalizând nivelurile. Apoi 4 și 5 urcă amândouă la 2, care este răspunsul.

Pentru u=2 și v=6, egalizarea îl aduce pe 6 chiar în 2, deci nu mai urcăm simultan. Pentru două vârfuri identice, răspunsul este acel vârf, conform convenției din definiție.

Tablourile clasice rezervă 1001 de poziții și folosesc 1..n. Timpul de pregătire este O(n), o întrebare consumă O(h), unde h este înălțimea arborelui, iar memoria este O(n). Pentru foarte multe întrebări, o metodă cu pregătire suplimentară poate reduce timpul per întrebare.

Exersează

Pe arborele exemplu, perechile (6,5), (2,6), (3,6) și (4,4) produc 2,2,1,4. Testează și arborele format numai din rădăcină. Verifică faptul că nu folosești tata[1]=0 ca răspuns valid.

Revezi vectorul de tați, proprietățile arborilor și parcurgerile.

Întrebări frecvente

Ce este cel mai apropiat strămoș comun?

Este strămoșul comun aflat la cea mai mare adâncime față de rădăcină. În convenția lecției, fiecare vârf este și propriul său strămoș.

Care este strămoșul comun al unui vârf cu el însuși?

Vârful respectiv. De asemenea, dacă u este strămoș al lui v, cel mai apropiat strămoș comun al lor este u.

Cum ajută vectorul de tați la găsirea strămoșului comun?

El permite urcarea către rădăcină. Poți marca strămoșii unui vârf și apoi urca din celălalt până la primul marcat, sau poți egaliza adâncimile înainte să urci simultan.