Number of Provinces

Q: Wie hoch ist die Zeitkomplexität der Anzahl der Provinzen?

O(n²) mit einer Graphensuche oder Union-Find, da beide jeden Eintrag der n × n -Matrix einmal auslesen. Union-Find fügt einen Faktor α(n) hinzu, die inverse Ackermann-Funktion, die in der Praxis höchstens 4 beträgt. Der zusätzliche Speicherbedarf ist O(n).

Q: Solltest du DFS, BFS oder Union-Find für die Anzahl der Provinzen verwenden?

Alle drei liefern dieselbe Anzahl in O(n²) Zeit zurück. DFS oder BFS lässt sich am kürzesten schreiben. Union-Find ist das bessere Werkzeug, wenn du außerdem viele Fragen der Form „Gehören diese beiden Städte zur selben Provinz?“ beantworten musst, da jede Antwort nahezu konstante Zeit benötigt.

Q: Wie unterscheidet sich die Anzahl der Provinzen von der Anzahl der Inseln?

Beide zählen Zusammenhangskomponenten. Bei „Number of Islands“ ist der Graph ein Raster, jedes Feld hat höchstens vier Nachbarn, und der Aufwand beträgt O(rows × cols). Hier ist der Graph eine Adjazenzmatrix: Jede Stadt kann mit jeder anderen verbunden sein, und um die Nachbarn einer Stadt aufzulisten, muss eine vollständige Zeile mit n Einträgen gelesen werden.

MittelUnion-Find Graphen

+10

Es gibt n Städte, nummeriert von 0 bis n-1. isConnected[i][j] ist 1, wenn eine Straße die Stadt i direkt mit der Stadt j verbindet, und andernfalls 0. Straßen sind in beide Richtungen befahrbar, daher ist die Matrix symmetrisch, und jede Stadt ist mit sich selbst verbunden.

Eine Provinz ist eine Gruppe von Städten, die sich alle gegenseitig erreichen können, direkt oder über andere Städte, wobei keine Straße aus der Gruppe hinausführt. Gib die Anzahl der Provinzen zurück.

Funktion

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

isConnectedinteger-2d-array: die n × n-Matrix, 1, wenn eine Straße zwei Städte direkt verbindet
Gibt zurückinteger: die Anzahl der Provinzen

Einschränkungen

1 ≤ n ≤ 150, wobei n = isConnected.length
isConnected[i].length = n
isConnected[i][j] ist 0 oder 1
isConnected[i][i] = 1
isConnected[i][j] = isConnected[j][i]

Beispiele

Eingabe: isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]
Ausgabe: 2
Erklärung: Stadt 0 hat eine Straße zur Stadt 3, und Stadt 1 hat eine Straße zur Stadt 2. Keine Straße verbindet die beiden Paare, daher gibt es 2 Provinzen.

Weiterführende Frage

Jede Straße wird nun an einem bestimmten Tag geöffnet. Kannst du den ersten Tag finden, an dem alle Städte zu einer einzigen Provinz gehören?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Die Matrix beschreibt einen ungerichteten Graphen: Städte sind Knoten und jede 1 ist eine Kante. Eine Provinz ist eine zusammenhängende Komponente, und eine 0 zwischen zwei Städten trennt sie nicht, wenn eine dritte Stadt beide verbindet. Eine Suche von jeder unbesuchten Stadt aus oder eine Union-Find-Struktur über alle Kanten zählt die Komponenten in O(n²).

Tiefensuche von jeder unbesuchten Stadt aus

Idee

Eine unmarkierte Stadt kann nicht zu einer Provinz gehören, die du bereits gezählt hast, denn jede Suche markiert ihre gesamte Provinz. Sie beginnt also eine neue. Die Suche folgt den Zeilen der Matrix: Im zweiten Beispiel erreicht die Suche von Stadt 0 aus Stadt 1, und die Zeile von Stadt 1 erreicht dann Stadt 2, obwohl in Zeile 0 für Stadt 2 eine 0 steht.

Jede Stadt wird einmal aus dem Stapel genommen und ihre Zeile mit n Einträgen gelesen, daher liest du die Matrix einmal: O(n²) Zeit. Die Markierungen und der Stapel enthalten höchstens n Städte, daher beträgt der zusätzliche Speicherplatz O(n).

Algorithmus

Erstelle für jede Stadt ein Kennzeichen dafür, ob sie bereits besucht wurde, und setze den Zähler auf 0.
Gehe die Städte der Reihe nach durch und überspringe jede Stadt, die bereits besucht wurde.
Erhöhe bei einer noch nicht besuchten Stadt den Zähler um 1, markiere sie und lege sie auf einen Stapel.
Solange sich Städte auf dem Stapel befinden, nimm eine herunter und lege jede Stadt in ihrer Zeile, deren Wert 1 ist und die noch nicht besucht wurde, auf den Stapel. Markiere sie dabei.
Gib den Zähler zurück.

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 mit Pfadkompression und Vereinigung nach Rang

Idee

Beginne mit n Provinzen, eine pro Stadt. Jede 1 oberhalb der Diagonale bedeutet, dass zwei Städte zusammengehören: Wenn ihre Gruppen verschieden sind, führe sie zusammen und verringere die Anzahl um eins. Im zweiten Beispiel beginnt die Anzahl bei 5, (0, 1) führt die Städte 0 und 1 zusammen, (1, 2) nimmt Stadt 2 in ihre Gruppe auf, und 3 Provinzen bleiben übrig.

Union-Find speichert jede Gruppe als Baum: parent[c] zeigt eine Ebene nach oben, und zwei Städte gehören zur selben Gruppe, wenn find beide zum selben Wurzelknoten hinaufgeht. Ohne Eingriffe können Zusammenführungen einen langen Pfad bilden, den jedes find in O(n) Schritten durchläuft. Union by rank hängt den kürzeren Baum unter den höheren, sodass kein Pfad länger als log n ist. Die Pfadkomprimierung lässt jede Stadt, die find durchlaufen hat, direkt auf die Wurzel zeigen. Zusammen sorgen sie dafür, dass jedes find amortisiert O(α(n)) benötigt, und α(n) ist in der Praxis höchstens 4.

Algorithmus

Setze parent[c] = c und rank[c] = 0 für jede Stadt und den Zähler auf n.
Finde für jedes Paar i < j mit isConnected[i][j] = 1 die Wurzeln von i und j.
Gehe in find bis zur Wurzel nach oben, durchlaufe dann den Pfad erneut und verweise jede Stadt darauf auf die Wurzel.
Wenn sich die Wurzeln unterscheiden, hänge die Wurzel mit dem niedrigeren Rang unter die andere, erhöhe bei Gleichstand den Rang um 1 und verringere den Zähler um 1.
Gib den Zähler zurück.

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

Stolperfallen und Grenzfälle

Sich nur auf direkte Straßen verlassen. Die Städte 0 und 2 im zweiten Beispiel haben eine 0 zwischen sich und gehören trotzdem zur selben Provinz.
Die Anzahl der 1en zählen und durch zwei teilen. Drei Städte, die alle miteinander verbunden sind, haben drei Straßen und eine Provinz.
Bei Union-Find den Zähler bei jeder 1 verringern, statt nur dann, wenn sich die beiden Wurzeln unterscheiden.
parent[i] mit parent[j] vergleichen. Zwei Städte in derselben Gruppe können unterschiedliche Eltern haben, wenn eine tiefer liegt; vergleiche find(i) mit find(j).
Stadt j selbst anhängen, wie in parent[j] = find(i). Wenn j bereits zu einer Gruppe gehörte, bleibt der Rest dieser Gruppe bei der Zusammenführung außen vor.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität der Anzahl der Provinzen?

O(n²) mit einer Graphensuche oder Union-Find, da beide jeden Eintrag der n × n-Matrix einmal auslesen. Union-Find fügt einen Faktor α(n) hinzu, die inverse Ackermann-Funktion, die in der Praxis höchstens 4 beträgt. Der zusätzliche Speicherbedarf ist O(n).

Solltest du DFS, BFS oder Union-Find für die Anzahl der Provinzen verwenden?

Alle drei liefern dieselbe Anzahl in O(n²) Zeit zurück. DFS oder BFS lässt sich am kürzesten schreiben. Union-Find ist das bessere Werkzeug, wenn du außerdem viele Fragen der Form „Gehören diese beiden Städte zur selben Provinz?“ beantworten musst, da jede Antwort nahezu konstante Zeit benötigt.

Wie unterscheidet sich die Anzahl der Provinzen von der Anzahl der Inseln?

Beide zählen Zusammenhangskomponenten. Bei „Number of Islands“ ist der Graph ein Raster, jedes Feld hat höchstens vier Nachbarn, und der Aufwand beträgt O(rows × cols). Hier ist der Graph eine Adjazenzmatrix: Jede Stadt kann mit jeder anderen verbunden sein, und um die Nachbarn einer Stadt aufzulisten, muss eine vollständige Zeile mit n Einträgen gelesen werden.

def findCircleNum(isConnected):
    # Schreibe hier den Code

Test #1

Test #2

Argument

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

Erwartete Ausgabe