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 è al massimo 4 per qualsiasi input reale. Lo spazio aggiuntivo è O(n) per i flag di visitato oppure per gli array parent e rank.

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

Tutti e tre restituiscono lo stesso conteggio in tempo O(n²). DFS o BFS sono i più rapidi da scrivere quando l'intera matrice viene fornita in una volta sola. Union-find è lo strumento migliore quando le strade arrivano una alla volta, oppure quando devi anche rispondere se due città condividono una provincia, perché gestisce ogni strada e ogni domanda in tempo quasi costante senza una nuova ricerca.

Q: Che cosa fanno la compressione del percorso e l’unione per rango nella struttura union-find?

L’unione per rango collega l’albero più corto sotto quello più alto quando due gruppi si fondono, mantenendo ogni albero alto al massimo log n. La compressione dei percorsi fa sì che ogni nodo attraversato da find punti direttamente alla radice, così le ricerche successive a partire da quei nodi richiedono un solo passaggio. Con entrambe, qualsiasi sequenza di m operazioni costa O(m α(n)), che si comporta come un tempo lineare.

Q: In che modo Number of Provinces è diverso da Number of Islands?

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

MedioUnion-find Grafi

+10

Ci sono n città, numerate da 0 a n-1. Ti viene fornita una matrice n × n isConnected come elenco di righe: isConnected[i][j] è 1 quando una strada collega direttamente la città i e la città j, e 0 quando non lo fa. Le strade funzionano in entrambe le direzioni, quindi la matrice è simmetrica, e ogni città è considerata collegata a sé stessa.

Una provincia è un gruppo di città che possono raggiungersi tutte tra loro, direttamente o passando per altre città, senza strade che conducano 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 o 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.

+15 test nascosti all’invio

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 è la matrice di adiacenza di un grafo non orientato: le città sono nodi e un 1 nella riga i, colonna j è un arco. Una provincia è una componente connessa, quindi la risposta è il numero di componenti. La trappola è che si può passare per una terza città: uno 0 tra due città non le colloca in province diverse. Una ricerca a partire da ogni città non visitata, oppure una struttura union-find che unisce gli estremi di ogni arco, conta le componenti in O(n²), la dimensione della matrice stessa.

Ricerca in profondità da ogni città non visitata

Intuizione

Attraversa le città in ordine. Quando incontri una città che nessuna ricerca precedente ha contrassegnato, non può appartenere a una provincia che hai già conteggiato, perché ogni ricerca contrassegna l’intera provincia. Aggiungi quindi uno al conteggio e contrassegna tutte le città che questa può raggiungere.

Per trovarle, tieni uno stack. Estrai una città, leggi la sua riga della matrice e inserisci nello stack ogni città con un 1 in quella riga che non è ancora contrassegnata, contrassegnandola mentre la inserisci. Nel secondo esempio, la ricerca dalla città 0 inserisce la città 1 e poi la riga della città 1 aggiunge la città 2, anche se la riga 0 ha uno 0 per la città 2. Seguire le righe in questo modo permette di individuare le città collegate solo tramite altre città.

Ogni città viene estratta una volta e, quando la estrai, leggi la sua riga di n elementi, quindi il tempo totale è O(n²): leggi la matrice una volta. I contrassegni e lo stack contengono al massimo n città, quindi lo spazio aggiuntivo è O(n).

Una ricerca ricorsiva è più leggibile, ma in una provincia disposta come una lunga linea le chiamate si annidano una volta per città. Con n = 150 è sicura; lo stesso codice su un grafo con 10^5 nodi fa traboccare lo stack delle chiamate, quindi vale la pena prendere l’abitudine di usare uno stack esplicito.

Algoritmo

Crea un flag di visitato per ogni città e imposta il conteggio a 0.
Esamina le città in ordine e salta quelle già visitate.
Per una città non visitata, aggiungi 1 al conteggio, contrassegnala e inseriscila in uno stack.
Mentre lo stack contiene città, estrai una città e inserisci nello stack ogni città della sua riga che ha un 1 e non è ancora stata visitata, contrassegnandola mentre la 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

Ribalta la domanda. Inizia con n province, una per città. Ogni 1 nella matrice indica che due città appartengono allo stesso gruppo: se sono ancora in gruppi diversi, unisci i gruppi e il conteggio diminuisce di uno. Dopo l’ultima strada, il conteggio è la risposta. Ti bastano le voci sopra la diagonale, perché la matrice è simmetrica e la diagonale collega una città a sé stessa. Nel secondo esempio il conteggio parte da 5. L’1 in (0, 1) unisce le città 0 e 1 (ne restano 4), e l’1 in (1, 2) rileva che la città 1 appartiene al gruppo della città 0 e vi aggiunge la città 2 (ne restano 3). Le città 3 e 4 non hanno alcun 1 sopra la diagonale, quindi la risposta è 3.

Una struttura union-find, chiamata anche unione di insiemi disgiunti, memorizza ogni gruppo come un albero. parent[c] punta al nodo immediatamente superiore, e la città in cima, il cui genitore è sé stessa, è la radice del gruppo. Due città appartengono allo stesso gruppo esattamente quando find risale da entrambe fino alla stessa radice. Per unire due gruppi, collega una radice all’altra.

Due regole mantengono gli alberi piatti. L’unione per rango collega l’albero più basso sotto quello più alto, così un albero di altezza h contiene almeno 2^h città e nessun percorso è più lungo di log n. La compressione del percorso fa un passo in più: una volta che find ha individuato la radice, collega direttamente a essa ogni città attraversata, così la ricerca successiva da una qualsiasi di esse richiede un solo passaggio. Senza nessuna delle due regole, unire le città di una lunga catena in un ordine sfortunato crea un albero che è un unico percorso, e ogni find percorre O(n) passaggi.

Con entrambe le regole, ogni find costa O(α(n)) ammortizzato, dove α è la funzione inversa di Ackermann, che rimane al massimo pari a 4 per qualsiasi n che un computer possa contenere. Leggere la matrice costa comunque O(n²), quindi questo è il costo totale, e gli array parent e rank richiedono O(n) spazio. La struttura è utile quando le strade arrivano una alla volta: mantiene aggiornato il conteggio dopo ogni nuova strada senza dover effettuare di nuovo la ricerca.

Algoritmo

Imposta parent[c] = c e rank[c] = 0 per ogni città e imposta il conteggio a n.
Per ogni coppia i < j con isConnected[i][j] = 1, trova le radici di i e j.
In find, risali fino alla radice, poi ripercorri lo stesso percorso e collega direttamente alla radice ogni città che si trova lungo il percorso.
Se le radici sono diverse, collega la radice con il 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

La maggior parte delle risposte errate considera uno 0 come prova che due città siano separate oppure conta qualcosa di diverso dalle componenti.

Controllare solo le strade dirette. Le città 0 e 2 nel secondo esempio hanno uno 0 tra loro e condividono comunque una provincia tramite la città 1. Qualsiasi conteggio basato solo sulle strade dirette non lo rileva; contare, per esempio, le righe distinte dà 5 invece di 3.
Contare gli 1 e dividere per due. In questo modo si contano le strade, non le province: tre città collegate tutte tra loro hanno tre strade e una provincia.
Nel union-find, diminuire il conteggio per ogni 1 invece di farlo solo quando le due radici sono diverse. Una strada all'interno di un gruppo già unito non deve modificare il conteggio.
Confrontare i genitori invece delle radici. parent[i] == parent[j] può essere falso per due città dello stesso gruppo quando una si trova più in profondità nell'albero; confronta sempre find(i) con find(j).
Collegare la città j stessa invece della sua radice, come in parent[j] = find(i). Se j apparteneva già a un gruppo, il resto di quel gruppo rimane escluso dall'unione.
Usare la ricorsione su grafi grandi. Una ricerca ricorsiva, o un find ricorsivo senza unione per rango, percorre un livello per città in un grafo a forma di catena. Va bene con 150 città, ma provoca un overflow dello stack con 10^5.

Domande frequenti4

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 è al massimo 4 per qualsiasi input reale. Lo spazio aggiuntivo è O(n) per i flag di visitato oppure per gli array parent e rank.

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

Tutti e tre restituiscono lo stesso conteggio in tempo O(n²). DFS o BFS sono i più rapidi da scrivere quando l'intera matrice viene fornita in una volta sola. Union-find è lo strumento migliore quando le strade arrivano una alla volta, oppure quando devi anche rispondere se due città condividono una provincia, perché gestisce ogni strada e ogni domanda in tempo quasi costante senza una nuova ricerca.

Che cosa fanno la compressione del percorso e l’unione per rango nella struttura union-find?

L’unione per rango collega l’albero più corto sotto quello più alto quando due gruppi si fondono, mantenendo ogni albero alto al massimo log n. La compressione dei percorsi fa sì che ogni nodo attraversato da find punti direttamente alla radice, così le ricerche successive a partire da quei nodi richiedono un solo passaggio. Con entrambe, qualsiasi sequenza di m operazioni costa O(m α(n)), che si comporta come un tempo lineare.

In che modo Number of Provinces è diverso da Number of Islands?

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

Python

def findCircleNum(isConnected):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Input

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

Atteso