Vai al contenuto principale

Informatica · Implementazione

Insiemi uniti collegando le radici

Si usano un array p, con p[x] = x all'inizio per ogni x da 1 a 10, e le funzioni

def trova(x):
    while p[x] != x:
        x = p[x]
    return x

def unisci(a, b):
    r = trova(a)
    s = trova(b)
    if r != s:
        p[r] = s

Si eseguono in ordine unisci(1, 2), unisci(3, 4), unisci(2, 4), unisci(5, 6), unisci(6, 7), unisci(1, 7), unisci(8, 5), unisci(3, 8), unisci(9, 10), unisci(10, 1), unisci(2, 9). Quante volte viene eseguita in tutto l'istruzione x = p[x]?

La tua risposta

Vanno bene sia 3,14 sia 3.14.