Esercizio 1 - Esonero Aprile 2024

[notedo]

[notedo]

def vettore_influenze(a, b, G):
    def BFSv(u, G):
        visitati = [[] for _ in range(len(G))]
        pila = [u]
        visitati[u] = 1
        i = 0
        distanze = [0 for _ in range(len(G))]
        distanze[u] = 0
        while len(pila) > i:
            u = pila[i]
            i += 1
            for y in G[u]:
                if not visitati[y]:
                    visitati[y] = 1
                    pila.append(y)
                    distanze[y] = distanze[u] + 1
        return distanze

    GT = inverti_grafo(G)
    av = BFSv(a, GT)
    bv = BFSv(b, GT)
    infv = [0 for _ in range(len(G))]

    for i in range(len(G)):
        aind = av[i]
        bind = bv[i]
        if aind == bind:
            infv[i] = -1
        elif aind < bind:
            infv[i] = a
        else:
            infv[i] = b

    return infv