Number of Provinces

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

O(n²) mit entweder 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 für jede reale Eingabe höchstens 4 beträgt. Der zusätzliche Speicherplatz beträgt O(n) für die Markierungen der besuchten Elemente oder für die Eltern- und Rang-Arrays.

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

Alle drei geben die gleiche Anzahl in O(n²)-Zeit zurück. DFS oder BFS lassen sich am kürzesten schreiben, wenn die gesamte Matrix auf einmal gegeben ist. Union-Find ist das bessere Werkzeug, wenn Straßen nach und nach hinzukommen oder wenn du auch beantworten musst, ob zwei Städte derselben Provinz angehören, denn damit lassen sich jede Straße und jede Frage in nahezu konstanter Zeit behandeln, ohne eine neue Suche durchzuführen.

Q: Was bewirken Pfadkompression und Vereinigung nach Rang in Union-Find?

Bei der Vereinigung nach Rang wird der kürzere Baum unter den höheren gehängt, wenn zwei Gruppen zusammengeführt werden. Dadurch ist jeder Baum höchstens log n hoch. Durch Pfadkompression zeigt jeder Knoten, den find durchläuft, direkt auf die Wurzel, sodass spätere Abfragen von diesen Knoten nur einen Schritt benötigen. Zusammen kosten beliebige Folgen von m Operationen O(m α(n)), was sich wie lineare Zeit verhält.

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

Beide zählen zusammenhängende Komponenten. Bei Number of Islands ist der Graph ein Raster, jedes Quadrat hat höchstens vier Nachbarn, und der Aufwand beträgt O(rows × cols). Hier liegt der Graph als Adjazenzmatrix vor: Jede Stadt kann mit jeder anderen verbunden sein, und du liest eine vollständige Zeile mit n Einträgen, um die Nachbarn einer Stadt aufzulisten.

MittelUnion-Find Graphen

+10

Es gibt n Städte, nummeriert von 0 bis n-1. Du erhältst eine n × n-Matrix isConnected als Liste von Zeilen: isConnected[i][j] ist 1, wenn eine Straße Stadt i und Stadt j direkt verbindet, und 0, wenn dies nicht der Fall ist. Straßen funktionieren in beide Richtungen, daher ist die Matrix symmetrisch, und jede Stadt gilt als mit sich selbst verbunden.

Eine Provinz ist eine Gruppe von Städten, die sich alle direkt oder über andere Städte erreichen können, wobei keine Straße aus der Gruppe herausfü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 zu Stadt 3, und Stadt 1 hat eine Straße zu Stadt 2. Keine Straße verbindet die beiden Paare, daher gibt es 2 Provinzen.

+15 versteckte Tests beim Einreichen

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 ist die Adjazenzmatrix eines ungerichteten Graphen: Städte sind Knoten, und eine 1 in Zeile i, Spalte j ist eine Kante. Eine Provinz ist eine zusammenhängende Komponente, daher ist die Antwort die Anzahl der Komponenten. Die Falle ist, dass eine Verbindung über eine dritte Stadt möglich ist: Eine 0 zwischen zwei Städten bedeutet nicht, dass sie zu verschiedenen Provinzen gehören. Eine Suche von jeder unbesuchten Stadt aus oder eine Union-Find-Struktur, die die beiden Endpunkte jeder Kante zusammenführt, zählt die Komponenten in O(n²), der Größe der Matrix selbst.

Tiefensuche von jeder unbesuchten Stadt aus

Idee

Gehe die Städte der Reihe nach durch. Wenn du auf eine Stadt triffst, die von keiner früheren Suche markiert wurde, kann sie nicht zu einer Provinz gehören, die du bereits gezählt hast, denn jede Suche markiert ihre gesamte Provinz. Erhöhe also den Zähler um eins und markiere dann jede Stadt, die von dieser aus erreichbar ist.

Um diese Städte zu finden, verwende einen Stack. Entferne eine Stadt vom Stack, lies ihre Zeile der Matrix und füge jede Stadt hinzu, für die in dieser Zeile eine 1 steht und die noch nicht markiert ist. Markiere sie dabei. Im zweiten Beispiel fügt die Suche ab Stadt 0 die Stadt 1 hinzu, und die Zeile von Stadt 1 fügt dann Stadt 2 hinzu, obwohl in Zeile 0 für Stadt 2 eine 0 steht. Wenn du die Zeilen auf diese Weise verfolgst, findest du auch Städte, die nur über andere Städte verbunden sind.

Jede Stadt wird einmal vom Stack entfernt, und dabei wird ihre Zeile mit n Einträgen gelesen. Insgesamt beträgt die Laufzeit also O(n²): Du liest die Matrix einmal. Die Markierungen und der Stack enthalten höchstens n Städte, der zusätzliche Speicherbedarf beträgt also O(n).

Eine rekursive Suche ist zwar übersichtlicher, aber bei einer Provinz, die wie eine lange Linie aufgebaut ist, werden die Funktionsaufrufe für jede Stadt verschachtelt. Bei n = 150 ist das unbedenklich; derselbe Code führt bei einem Graphen mit 10^5 Knoten zu einem Überlauf des Aufrufstacks. Daher solltest du dir den expliziten Stack angewöhnen.

Algorithmus

Lege für jede Stadt eine Markierung an, 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, für die eine 1 steht und die noch nicht besucht wurde, darauf; 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

Drehe die Frage um. Beginne mit n Provinzen, einer pro Stadt. Jede 1 in der Matrix besagt, dass zwei Städte zusammengehören: Wenn sie noch in verschiedenen Gruppen sind, führe die Gruppen zusammen, und die Anzahl sinkt um eins. Nach der letzten Straße ist die Anzahl die Antwort. Du brauchst nur die Einträge oberhalb der Diagonalen, weil die Matrix symmetrisch ist und die Diagonale eine Stadt mit sich selbst verbindet. Im zweiten Beispiel beginnt die Anzahl bei 5. Die 1 bei (0, 1) führt die Städte 0 und 1 zusammen (4 übrig), und bei der 1 bei (1, 2) wird festgestellt, dass Stadt 1 zur Gruppe von Stadt 0 gehört, und Stadt 2 wird ebenfalls in diese Gruppe aufgenommen (3 übrig). Für die Städte 3 und 4 gibt es oberhalb der Diagonalen keine 1, also ist die Antwort 3.

Eine Union-Find-Struktur, auch disjunkte Mengenvereinigung genannt, speichert jede Gruppe als Baum. parent[c] verweist eine Ebene nach oben, und die Stadt an der Spitze, deren Elternknoten sie selbst ist, ist die Wurzel der Gruppe. Zwei Städte sind genau dann in derselben Gruppe, wenn find bei beiden zur selben Wurzel hinaufgeht. Um zwei Gruppen zusammenzuführen, verweist man eine Wurzel auf die andere.

Zwei Regeln halten die Bäume flach. Vereinigung nach Rang hängt den kürzeren Baum unter den höheren, sodass ein Baum der Höhe h mindestens 2^h Städte enthält und kein Pfad länger als log n ist. Pfadkompression geht noch weiter: Sobald find die Wurzel gefunden hat, verweist die Funktion jede Stadt, die sie durchlaufen hat, direkt auf diese Wurzel, sodass die nächste Suche von jeder dieser Städte aus nur einen Schritt benötigt. Ohne eine der beiden Regeln führt das Zusammenführen der Städte einer langen Kette in einer ungünstigen Reihenfolge zu einem Baum, der nur aus einem einzigen Pfad besteht, und jedes find durchläuft O(n) Schritte.

Mit beiden Regeln kostet jedes find amortisiert O(α(n)), wobei α die inverse Ackermann-Funktion ist, die für jedes n, das ein Computer speichern kann, höchstens 4 beträgt. Das Einlesen der Matrix kostet weiterhin O(n²), also ist das die Gesamtlaufzeit, und die parent- und rank-Arrays benötigen O(n) Speicherplatz. Die Struktur bewährt sich, wenn Straßen eine nach der anderen hinzukommen: Sie hält die Anzahl nach jeder neuen Straße aktuell, ohne erneut suchen zu müssen.

Algorithmus

Setze für jede Stadt parent[c] = c und rank[c] = 0 und setze den Zähler auf n.
Suche für jedes Paar i < j mit isConnected[i][j] = 1 die Wurzeln von i und j.
Gehe in find bis zur Wurzel hinauf, durchlaufe dann denselben Pfad erneut und verweise jede Stadt darauf direkt 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

Die meisten falschen Antworten behandeln eine 0 als Beweis dafür, dass zwei Städte nicht verbunden sind, oder zählen etwas anderes als Komponenten.

Nur direkte Straßen prüfen. Die Städte 0 und 2 im zweiten Beispiel haben eine 0 zwischen sich und gehören trotzdem über Stadt 1 zur selben Provinz. Jede Zählung, die nur auf direkten Straßen basiert, übersieht das; zählt man beispielsweise die unterschiedlichen Zeilen, erhält man dort 5 statt 3.
Die 1en zählen und durch zwei teilen. Das zählt Straßen, nicht Provinzen: 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. Eine Straße innerhalb einer bereits zusammengeführten Gruppe darf den Zähler nicht verändern.
Elternknoten statt Wurzeln vergleichen. parent[i] == parent[j] kann für zwei Städte derselben Gruppe falsch sein, wenn eine im Baum tiefer liegt; vergleiche immer find(i) mit find(j).
Stadt j selbst statt ihrer Wurzel anhängen, wie bei parent[j] = find(i). Wenn j bereits zu einer Gruppe gehörte, wird der Rest dieser Gruppe von der Zusammenführung abgeschnitten.
Rekursion bei großen Graphen. Eine rekursive Suche oder ein rekursives find ohne Union by Rank geht in einem kettenförmigen Graphen pro Stadt eine Ebene tiefer. Bei 150 Städten ist das in Ordnung, bei 10^5 führt es zu einem Stack Overflow.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von „Anzahl der Provinzen“?

O(n²) mit entweder 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 für jede reale Eingabe höchstens 4 beträgt. Der zusätzliche Speicherplatz beträgt O(n) für die Markierungen der besuchten Elemente oder für die Eltern- und Rang-Arrays.

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

Alle drei geben die gleiche Anzahl in O(n²)-Zeit zurück. DFS oder BFS lassen sich am kürzesten schreiben, wenn die gesamte Matrix auf einmal gegeben ist. Union-Find ist das bessere Werkzeug, wenn Straßen nach und nach hinzukommen oder wenn du auch beantworten musst, ob zwei Städte derselben Provinz angehören, denn damit lassen sich jede Straße und jede Frage in nahezu konstanter Zeit behandeln, ohne eine neue Suche durchzuführen.

Was bewirken Pfadkompression und Vereinigung nach Rang in Union-Find?

Bei der Vereinigung nach Rang wird der kürzere Baum unter den höheren gehängt, wenn zwei Gruppen zusammengeführt werden. Dadurch ist jeder Baum höchstens log n hoch. Durch Pfadkompression zeigt jeder Knoten, den find durchläuft, direkt auf die Wurzel, sodass spätere Abfragen von diesen Knoten nur einen Schritt benötigen. Zusammen kosten beliebige Folgen von m Operationen O(m α(n)), was sich wie lineare Zeit verhält.

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

Beide zählen zusammenhängende Komponenten. Bei Number of Islands ist der Graph ein Raster, jedes Quadrat hat höchstens vier Nachbarn, und der Aufwand beträgt O(rows × cols). Hier liegt der Graph als Adjazenzmatrix vor: Jede Stadt kann mit jeder anderen verbunden sein, und du liest eine vollständige Zeile mit n Einträgen, um die Nachbarn einer Stadt aufzulisten.

Python

def findCircleNum(isConnected):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Eingabe

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

Erwartet