Number of Provinces

Q: Qual è la complessità temporale di Number of Provinces?

O(n²) con una ricerca nel grafo o con union-find, perché entrambi leggono una volta ogni voce della matrice n × n . Union-find aggiunge un fattore α(n), la funzione inversa di Ackermann, che in pratica è al massimo 4. Lo spazio aggiuntivo è O(n).

Q: Dovresti usare DFS, BFS o union-find per il numero di province?

Tutti e tre restituiscono lo stesso conteggio in tempo O(n²). La DFS o la BFS sono le soluzioni più brevi da scrivere. Union-find è lo strumento migliore quando devi anche rispondere a molte domande del tipo «queste due città appartengono alla stessa provincia?», perché ogni risposta richiede un tempo quasi costante.

Q: In che modo il numero di province è diverso dal numero di isole?

Entrambi contano le componenti connesse. In Number of Islands il grafo è una griglia, ogni casella ha al massimo quattro vicini e il lavoro è O(righe × colonne). Qui il grafo è una matrice di adiacenza: qualsiasi città può essere collegata a qualsiasi altra e, per elencare i vicini di una città, si legge un'intera riga di n elementi.

MedioUnion-find Grafi

+10

Ci sono n città, numerate da 0 a n-1. isConnected[i][j] è 1 quando una strada collega direttamente la città i e la città j, e 0 altrimenti. Le strade funzionano in entrambe le direzioni, quindi la matrice è simmetrica e ogni città è collegata a se stessa.

Una provincia è un gruppo di città che possono raggiungersi tutte tra loro, direttamente o passando per altre città, senza che alcuna strada conduca fuori dal gruppo. Restituisci il numero di province.

Funzione

findCircleNum(isConnected: integer-2d-array) → integer

isConnectedinteger-2d-array: la matrice n × n, 1 dove una strada collega direttamente due città
Restituisceinteger: il numero di province

Vincoli

1 ≤ n ≤ 150, dove n = isConnected.length
isConnected[i].length = n
isConnected[i][j] è 0 oppure 1
isConnected[i][i] = 1
isConnected[i][j] = isConnected[j][i]

Esempi

Input: isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]
Output: 2
Spiegazione: La città 0 ha una strada che porta alla città 3 e la città 1 ha una strada che porta alla città 2. Nessuna strada collega le due coppie, quindi ci sono 2 province.

Per approfondire

Ogni strada ora si apre in un determinato giorno. Riesci a trovare il primo giorno in cui tutte le città appartengono a un'unica provincia?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

La matrice descrive un grafo non orientato: le città sono nodi e ogni 1 è un arco. Una provincia è una componente connessa e uno 0 tra due città non le separa quando una terza città le collega entrambe. Una ricerca da ogni città non visitata, oppure una struttura union-find su ogni arco, conta le componenti in O(n²).

Ricerca in profondità da ogni città non visitata

Intuizione

Una città non contrassegnata non può appartenere a una provincia che hai già contato, perché ogni ricerca contrassegna l'intera provincia. Quindi ne inizia una nuova. La ricerca segue le righe della matrice: nel secondo esempio, la ricerca dalla città 0 raggiunge la città 1, e la riga della città 1 raggiunge poi la città 2, anche se la riga 0 contiene uno 0 per la città 2.

Ogni città viene estratta una sola volta e legge la propria riga di n elementi, quindi leggi la matrice una sola volta: tempo O(n²). I contrassegni e la pila contengono al massimo n città, quindi lo spazio aggiuntivo è O(n).

Algoritmo

Crea un contrassegno di visita per ogni città e imposta il conteggio su 0.
Esamina le città in ordine e salta quelle già visitate.
Per una città non ancora visitata, aggiungi 1 al conteggio, contrassegnala e inseriscila in una pila.
Finché la pila contiene città, estrai una città e inserisci nella pila tutte le città della sua riga che hanno un 1 e non sono ancora state visitate, contrassegnandole man mano che le inserisci.
Restituisci il conteggio.

def findCircleNum(isConnected):
    n = len(isConnected)
    seen = [False] * n
    provinces = 0
    for start in range(n):
        if seen[start]:
            continue
        # Nobody reached this city from an earlier province, so it starts a new one.
        provinces += 1
        seen[start] = True
        stack = [start]
        while stack:
            city = stack.pop()
            row = isConnected[city]
            for other in range(n):
                # Mark a city when you push it, so it is never pushed twice.
                if row[other] == 1 and not seen[other]:
                    seen[other] = True
                    stack.append(other)
    return provinces

Union-find con compressione del cammino e unione per rango

Intuizione

Inizia con n province, una per città. Ogni 1 sopra la diagonale indica che due città appartengono allo stesso gruppo: se i loro gruppi sono diversi, uniscili e riduci il conteggio di uno. Nel secondo esempio il conteggio parte da 5, (0, 1) unisce le città 0 e 1, (1, 2) aggiunge la città 2 al loro gruppo e restano 3 province.

Union-find memorizza ogni gruppo come un albero: parent[c] punta al nodo superiore di un livello e due città condividono un gruppo quando find le porta entrambe alla stessa radice. Se lasciate sole, le unioni possono creare un percorso molto lungo che ogni find percorre in O(n) passaggi. L’unione per rango colloca l’albero più corto sotto quello più alto, così nessun percorso supera log n. La compressione del percorso fa puntare direttamente alla radice ogni città attraversata da find. Insieme, rendono il costo ammortizzato di ogni find pari a O(α(n)); nella pratica, α(n) è al massimo 4.

Algoritmo

Imposta parent[c] = c e rank[c] = 0 per ogni città e imposta il conteggio su n.
Per ogni coppia i < j per cui isConnected[i][j] = 1, trova le radici di i e j.
In find, risali fino alla radice, poi ripercorri il percorso e fai puntare alla radice ogni città che si trova su di esso.
Se le radici sono diverse, collega la radice di rango inferiore sotto l'altra, aumenta di 1 il rango in caso di parità e sottrai 1 dal conteggio.
Restituisci il conteggio.

def findCircleNum(isConnected):
    n = len(isConnected)
    parent = list(range(n))
    rank = [0] * n

    def find(city):
        root = city
        while parent[root] != root:
            root = parent[root]
        # Path compression: point every city on the way straight at the root.
        while parent[city] != root:
            up = parent[city]
            parent[city] = root
            city = up
        return root

    provinces = n
    for i in range(n):
        for j in range(i + 1, n):  # the matrix is symmetric, so the upper half is enough
            if isConnected[i][j] == 1:
                a, b = find(i), find(j)
                if a == b:
                    continue
                # Union by rank: hang the shorter tree under the taller one.
                if rank[a] < rank[b]:
                    a, b = b, a
                parent[b] = a
                if rank[a] == rank[b]:
                    rank[a] += 1
                # Two provinces just became one.
                provinces -= 1
    return provinces

Trappole e casi limite

Fidarsi solo delle strade dirette. Le città 0 e 2 nel secondo esempio hanno uno 0 tra loro e fanno comunque parte della stessa provincia.
Contare gli 1 e dividere per due. Tre città collegate tutte tra loro hanno tre strade e una provincia.
In union-find, diminuire il conteggio per ogni 1 invece di farlo solo quando le due radici sono diverse.
Confrontare parent[i] con parent[j]. Due città nello stesso gruppo possono avere genitori diversi quando una si trova a una maggiore profondità; confronta find(i) con find(j).
Collegare la città j stessa, come in parent[j] = find(i). Se j faceva già parte di un gruppo, il resto di quel gruppo viene escluso dall'unione.

Domande frequenti3

Qual è la complessità temporale di Number of Provinces?

O(n²) con una ricerca nel grafo o con union-find, perché entrambi leggono una volta ogni voce della matrice n × n. Union-find aggiunge un fattore α(n), la funzione inversa di Ackermann, che in pratica è al massimo 4. Lo spazio aggiuntivo è O(n).

Dovresti usare DFS, BFS o union-find per il numero di province?

Tutti e tre restituiscono lo stesso conteggio in tempo O(n²). La DFS o la BFS sono le soluzioni più brevi da scrivere. Union-find è lo strumento migliore quando devi anche rispondere a molte domande del tipo «queste due città appartengono alla stessa provincia?», perché ogni risposta richiede un tempo quasi costante.

In che modo il numero di province è diverso dal numero di isole?

Entrambi contano le componenti connesse. In Number of Islands il grafo è una griglia, ogni casella ha al massimo quattro vicini e il lavoro è O(righe × colonne). Qui il grafo è una matrice di adiacenza: qualsiasi città può essere collegata a qualsiasi altra e, per elencare i vicini di una città, si legge un'intera riga di n elementi.

def findCircleNum(isConnected):
    # Scrivi il codice qui

Test #1

Test #2

Argomento

isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]

Output atteso