30 maggio 2024 - esercizio 1

[Elia-Belli]

[Elia-Belli]

Ripercorrendo il vettore dei padri a partire da un qualsiasi nodo possiamo calcolare se tra i suoi antenati c'è $u$ , per evitare di ricalcolare l'appartenenza al sottoalbero $T_u$ di nodi già analizzati, manteniamo un array $Vis[v]$ che per ogni nodo $v$ indica se appartiene a $T_u$ $(1)$, se non vi appartiene $(0)$ o se non è ancora stato stabilito $(-1)$ : un figlio che non conosce ancora la sua discendenza effettuerà una chiamata ricorsiva al padre ed al ritorno scoprirà se appartiene o meno a $T_u$.

• Complessità: $O(n)$ , ogni nodo è visitato al massimo una volta

def sotto_albero(P,u):
    Vis = [-1]*n
    Vis[u] = 1

    for v in P:
        if(Vis[v] == -1):
            visita(P,v,Vis)
    
    T_u = []
    for v in Vis:
        if(Vis[v] == 1): T_u.append(v)
    
    return T_u

def visita(P,v,Vis):
     
    if(Vis[P[v]] != -1):
        Vis[v] = Vis[P[v]]
        return Vis[v]

    r = 0
    if(P[v] != v):
        r = visita(P,P[v],Vis)

    Vis[v] = r
    return r

[CiottoloMaggico]

[CarloDaRomadev]