padri & distanza dalla radice

[CuriousCI]

Dato un albero rappresentato come vettore di padri scrivere lo pseudocodice di un algoritmo che trova la distanza dalla radice di ogni nodo dell'albero in $O(n)$

[CuriousCI]

fn distance_from_big_daddy(tree: &[usize]) -> Vec<Option<usize>> {
    let mut distance: Vec<Option<usize>> = vec![None; tree.len()];

    for x in 0..tree.len() {
        distance_from_big_daddy_rec(tree, x, &mut distance);
    }

    distance
}

fn distance_from_big_daddy_rec(
    tree: &[usize],
    x: usize,
    distance: &mut Vec<Option<usize>>,
) -> usize {
    if x == tree[x] {
        distance[x] = Some(0);
        return 0;
    }

    match distance[x] {
        Some(d) => d,
        None => {
            let d = distance_from_big_daddy_rec(tree, tree[x], distance);
            distance[x] = Some(d + 1);
            d
        }
    }
}

[LeoCosta02]

Global function main(P:vettore di padri ){
int Dist[n]=[-1...-1]
GLOBAL int check[n]=[0...0]
 for each(v appartenente a V(G)){
   if(check[v]==0)
   Dist_ric(P,Dist,v)
 }
 return Dist
}


Dist ric(P vettore padri, Dist, y vertice){ // chiamata ricorsiva che calcola la distanza dalla radice di y e di tutti gli antenati di y 
	if(P[y]==y){
	Dist[y]=0
         check[y]=1
	return 0
	}
	 if(Dist[P[y]]>=0){ // se hai gia calcolato la distanza del padre allora: 
	  Dist[y]=Dist[P[y]]+1
          check[y]=1
	  return Dist[y]
	 }	
		Dist[y]=Dist ric(P,Dist,P[y])+1
                check[y]=1
		return Dist[y]
}

[CasuFrost]

[CasuFrost]

alla riga 5 dell'algoritmo $dist$ volevo scrivere
if(Dist[i]) != -1 )