Number of Provinces

Q: Jaka jest złożoność czasowa problemu Number of Provinces?

O(n²) w przypadku wyszukiwania w grafie lub struktury union-find, ponieważ obie odczytują każdy wpis macierzy n × n jeden raz. Struktura union-find dodaje czynnik α(n), czyli odwrotną funkcję Ackermanna, która w praktyce wynosi najwyżej 4. Dodatkowe zużycie pamięci wynosi O(n).

Q: Czy do rozwiązania problemu liczby prowincji należy użyć DFS, BFS czy struktury union-find?

Wszystkie trzy zwracają tę samą liczbę w czasie O(n²). DFS lub BFS są najkrótsze do napisania. Struktura union-find jest lepszym narzędziem, gdy musisz też odpowiadać na wiele pytań w rodzaju „czy te dwa miasta należą do tej samej prowincji”, ponieważ każda odpowiedź zajmuje niemal stały czas.

Q: Czym Number of Provinces różni się od Number of Islands?

Oba rozwiązania zliczają składowe spójności. W Number of Islands graf jest siatką, każde pole ma najwyżej czterech sąsiadów, a złożoność wynosi O(rows × cols). Tutaj graf jest macierzą sąsiedztwa: każde miasto może być połączone z dowolnym innym, a wypisanie sąsiadów jednego miasta wymaga odczytania całego wiersza złożonego z n wpisów.

ŚrednieUnion-find Grafy

+10

Jest n miast, ponumerowanych od 0 do n-1. isConnected[i][j] ma wartość 1, gdy droga bezpośrednio łączy miasto i z miastem j, a w przeciwnym razie 0. Drogi działają w obie strony, więc macierz jest symetryczna, a każde miasto jest połączone samo ze sobą.

Prowincja to grupa miast, z których każde może dotrzeć do pozostałych bezpośrednio lub przez inne miasta, i z której nie prowadzi żadna droga na zewnątrz. Zwróć liczbę prowincji.

Funkcja

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

isConnectedinteger-2d-array: macierz n × n, 1 tam, gdzie droga łączy bezpośrednio dwa miasta
Zwracainteger: liczba prowincji

Ograniczenia

1 ≤ n ≤ 150, gdzie n = isConnected.length
isConnected[i].length = n
isConnected[i][j] ma wartość 0 lub 1
isConnected[i][i] = 1
isConnected[i][j] = isConnected[j][i]

Przykłady

Wejście: isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]
Wyjście: 2
Wyjaśnienie: Miasto 0 ma drogę do miasta 3, a miasto 1 ma drogę do miasta 2. Żadna droga nie łączy tych dwóch par, więc są 2 prowincje.

Pytanie dodatkowe

Każda droga jest teraz otwierana w określonym dniu. Czy potrafisz znaleźć pierwszy dzień, w którym wszystkie miasta należą do jednej prowincji?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Macierz opisuje graf nieskierowany: miasta są węzłami, a każda 1 jest krawędzią. Prowincja to spójna składowa, a 0 między dwoma miastami nie rozdziela ich, gdy oba łączy trzecie miasto. Przeszukiwanie rozpoczynane od każdego nieodwiedzonego miasta lub struktura union-find obejmująca każdą krawędź pozwala policzyć składowe w O(n²).

Przeszukiwanie w głąb z każdego nieodwiedzonego miasta

Intuicja

Nieoznaczone miasto nie może należeć do prowincji, którą już policzono, ponieważ każde wyszukiwanie oznacza całą swoją prowincję. Zatem rozpoczyna nową. Wyszukiwanie przebiega wierszami macierzy: w drugim przykładzie wyszukiwanie z miasta 0 dociera do miasta 1, a wiersz miasta 1 prowadzi następnie do miasta 2, mimo że wiersz 0 zawiera 0 dla miasta 2.

Każde miasto jest zdejmowane ze stosu raz i odczytuje swój wiersz z n wpisami, więc macierz jest odczytywana raz: czas O(n²). Oznaczenia i stos przechowują najwyżej n miast, więc dodatkowa pamięć wynosi O(n).

Algorytm

Utwórz flagę odwiedzenia dla każdego miasta i ustaw licznik na 0.
Przejdź przez miasta po kolei i pomiń każde miasto, które zostało już odwiedzone.
Dla nieodwiedzonego miasta zwiększ licznik o 1, oznacz je i umieść na stosie.
Dopóki na stosie są miasta, zdejmij jedno z nich i umieść na stosie każde miasto w jego wierszu, które ma wartość 1 i nie zostało jeszcze odwiedzone, oznaczając je podczas umieszczania.
Zwróć licznik.

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

Struktura union-find z kompresją ścieżki i łączeniem według rangi

Intuicja

Zacznij od n prowincji, po jednej na miasto. Każda 1 nad przekątną oznacza, że dwa miasta należą do tej samej grupy: jeśli należą do różnych grup, połącz je i zmniejsz liczbę o jeden. W drugim przykładzie liczba zaczyna się od 5, (0, 1) łączy miasta 0 i 1, (1, 2) dołącza miasto 2 do ich grupy, a pozostają 3 prowincje.

Struktura union-find przechowuje każdą grupę jako drzewo: parent[c] wskazuje o jeden poziom wyżej, a dwa miasta należą do tej samej grupy, gdy find prowadzi oba do tego samego korzenia. Bez dodatkowych optymalizacji operacje łączenia mogą utworzyć jedną długą ścieżkę, którą każda operacja find przechodzi w O(n) krokach. Łączenie według rangi dołącza niższe drzewo pod wyższym, dzięki czemu żadna ścieżka nie jest dłuższa niż log n. Kompresja ścieżek kieruje każde miasto, przez które przeszła operacja find, bezpośrednio do korzenia. Razem sprawiają, że zamortyzowana złożoność każdej operacji find wynosi O(α(n)), a α(n) w praktyce nie przekracza 4.

Algorytm

Ustaw parent[c] = c i rank[c] = 0 dla każdego miasta, a licznik ustaw na n.
Dla każdej pary i < j, dla której isConnected[i][j] = 1, znajdź korzenie i i j.
W find przejdź w górę do korzenia, a następnie ponownie przejdź ścieżkę i wskaż korzeń jako rodzica każdego miasta na tej ścieżce.
Jeśli korzenie są różne, dołącz korzeń o niższej randze do drugiego, przy remisie zwiększ rangę o 1 i zmniejsz licznik o 1.
Zwróć licznik.

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

Pułapki i przypadki brzegowe

Zakładanie, że drogi są tylko bezpośrednie. Miasta 0 i 2 w drugim przykładzie mają między sobą 0, a mimo to należą do tej samej prowincji.
Liczenie jedynek i dzielenie wyniku przez dwa. Trzy miasta, z których każde jest połączone z pozostałymi, mają trzy drogi i jedną prowincję.
W union-find zmniejszanie licznika przy każdej jedynce zamiast tylko wtedy, gdy oba korzenie są różne.
Porównywanie parent[i] z parent[j]. Dwa miasta w jednej grupie mogą mieć różnych rodziców, gdy jedno z nich znajduje się głębiej; porównaj find(i) z find(j).
Dołączanie samego miasta j, jak w parent[j] = find(i). Jeśli j należało już do grupy, pozostała część tej grupy nie zostanie połączona.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu Number of Provinces?

O(n²) w przypadku wyszukiwania w grafie lub struktury union-find, ponieważ obie odczytują każdy wpis macierzy n × n jeden raz. Struktura union-find dodaje czynnik α(n), czyli odwrotną funkcję Ackermanna, która w praktyce wynosi najwyżej 4. Dodatkowe zużycie pamięci wynosi O(n).

Czy do rozwiązania problemu liczby prowincji należy użyć DFS, BFS czy struktury union-find?

Wszystkie trzy zwracają tę samą liczbę w czasie O(n²). DFS lub BFS są najkrótsze do napisania. Struktura union-find jest lepszym narzędziem, gdy musisz też odpowiadać na wiele pytań w rodzaju „czy te dwa miasta należą do tej samej prowincji”, ponieważ każda odpowiedź zajmuje niemal stały czas.

Czym Number of Provinces różni się od Number of Islands?

Oba rozwiązania zliczają składowe spójności. W Number of Islands graf jest siatką, każde pole ma najwyżej czterech sąsiadów, a złożoność wynosi O(rows × cols). Tutaj graf jest macierzą sąsiedztwa: każde miasto może być połączone z dowolnym innym, a wypisanie sąsiadów jednego miasta wymaga odczytania całego wiersza złożonego z n wpisów.

def findCircleNum(isConnected):
    # Wpisz tutaj kod

Test #1

Test #2

Argument

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

Oczekiwany wynik