Number of Provinces

Q: Jaka jest złożoność czasowa problemu „Liczba prowincji”?

O(n²) zarówno w przypadku przeszukiwania grafu, jak i struktury union-find, ponieważ oba rozwiązania odczytują każdy element macierzy n × n jeden raz. Struktura union-find dodaje czynnik α(n), odwrotną funkcję Ackermanna, która dla każdego rzeczywistego argumentu jest co najwyżej równa 4. Dodatkowe miejsce wynosi O(n) na flagi odwiedzenia albo na tablice rodziców i rang.

Q: Czy do zadania Number of Provinces użyć DFS, BFS czy union-find?

Wszystkie trzy zwracają tę samą liczbę w czasie O(n²). DFS lub BFS najłatwiej napisać, gdy cała macierz jest dostępna od razu. Union-find jest lepszym narzędziem, gdy drogi pojawiają się pojedynczo albo gdy trzeba również odpowiedzieć na pytanie, czy dwa miasta należą do tej samej prowincji, ponieważ obsługuje każdą drogę i każde pytanie w niemal stałym czasie, bez konieczności ponownego wyszukiwania.

Q: Co robią kompresja ścieżki i łączenie według rangi w strukturze union-find?

Łączenie według rangi dołącza krótsze drzewo pod wyższym, gdy dwie grupy są łączone, dzięki czemu każde drzewo ma wysokość co najwyżej log n. Kompresja ścieżek sprawia, że każdy węzeł, przez który przechodzi find , wskazuje bezpośrednio na korzeń, więc późniejsze wyszukiwania rozpoczynające się w tych węzłach wymagają jednego kroku. Przy zastosowaniu obu metod dowolna sekwencja m operacji kosztuje O(m α(n)), co zachowuje się jak czas liniowy.

Q: Jaka jest różnica między liczbą prowincji a liczbą wysp?

Oba rozwiązania liczą spójne składowe. W zadaniu Number of Islands graf ma postać siatki, każde pole ma najwyżej czterech sąsiadów, a złożoność wynosi O(rows × cols). Tutaj graf jest przedstawiony w postaci macierzy sąsiedztwa: każde miasto może być połączone z dowolnym innym, a żeby wypisać sąsiadów jednego miasta, odczytujesz cały wiersz zawierający n wpisów.

ŚrednieUnion-find Grafy

+10

Jest n miast ponumerowanych od 0 do n-1. Otrzymujesz macierz n × n isConnected w postaci listy wierszy: isConnected[i][j] ma wartość 1, gdy droga łączy bezpośrednio miasto i z miastem j, a 0, gdy tak nie jest. Drogi działają w obu kierunkach, więc macierz jest symetryczna, a każde miasto jest uznawane za 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, gdy 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.

+15 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Każda droga otwiera się w określonym dniu. Czy potrafisz znaleźć pierwszy dzień, w którym wszystkie miasta będą należeć do jednej prowincji?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Macierz jest macierzą sąsiedztwa nieskierowanego grafu: miasta są wierzchołkami, a 1 w wierszu i, kolumnie j oznacza krawędź. Prowincja jest spójną składową, więc odpowiedzią jest liczba składowych. Pułapką jest połączenie przez trzecie miasto: 0 między dwoma miastami nie oznacza, że należą do różnych prowincji. Przeszukiwanie rozpoczynane od każdego nieodwiedzonego miasta lub struktura union-find łącząca oba końce każdej krawędzi zlicza składowe w czasie O(n²), czyli rozmiarze samej macierzy.

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

Intuicja

Przejdź kolejno przez miasta. Gdy trafisz na miasto, którego nie oznaczyło żadne wcześniejsze wyszukiwanie, nie może ono należeć do prowincji, którą już policzono, ponieważ każde wyszukiwanie oznacza całą swoją prowincję. Zwiększ więc licznik o jeden, a następnie oznacz każde miasto, do którego można dotrzeć z tego miasta.

Aby je znaleźć, używaj stosu. Zdejmij ze stosu miasto, odczytaj jego wiersz macierzy i dodaj na stos każde miasto, przy którym w tym wierszu znajduje się 1 i które nie zostało jeszcze oznaczone; oznacz je w chwili dodawania na stos. W drugim przykładzie wyszukiwanie rozpoczęte w mieście 0 dodaje na stos miasto 1, a następnie wiersz miasta 1 dodaje miasto 2, mimo że wiersz 0 zawiera 0 przy mieście 2. Podążanie w ten sposób za kolejnymi wierszami pozwala znaleźć miasta połączone tylko za pośrednictwem innych.

Każde miasto jest zdejmowane ze stosu raz, a zdjęcie go wymaga odczytania jego wiersza zawierającego n wpisów, więc łączny czas wynosi O(n²): macierz jest odczytywana raz. Oznaczenia i stos przechowują co najwyżej n miast, więc dodatkowa przestrzeń wynosi O(n).

Wyszukiwanie rekurencyjne jest czytelniejsze, ale w prowincji ukształtowanej jak jedna długa linia wywołania zagnieżdżają się po jednym na każde miasto. Przy n = 150 jest to bezpieczne; ten sam kod w grafie z 10^5 węzłów przepełnia stos wywołań, dlatego warto wyrobić sobie nawyk używania jawnego stosu.

Algorytm

Utwórz flagę odwiedzenia dla każdego miasta i ustaw licznik na 0.
Przejdź po miastach w kolejności 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.
Gdy na stosie są miasta, zdejmij jedno i umieść na stosie każde miasto z jego wiersza, które ma wartość 1 i nie zostało jeszcze odwiedzone, oznaczając je podczas umieszczania na stosie.
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

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

Intuicja

Odwróć pytanie. Zacznij od n prowincji, po jednej na każde miasto. Każda wartość 1 w macierzy oznacza, że dwa miasta należą do tej samej grupy: jeśli nadal należą do różnych grup, połącz te grupy, a liczba zmniejszy się o jeden. Po ostatniej drodze liczba ta jest odpowiedzią. Wystarczy sprawdzić elementy nad przekątną, ponieważ macierz jest symetryczna, a przekątna łączy miasto samo ze sobą. W drugim przykładzie liczba początkowa wynosi 5. Wartość 1 na pozycji (0, 1) łączy miasta 0 i 1 (zostają 4), a wartość 1 na pozycji (1, 2) pokazuje, że miasto 1 należy do grupy miasta 0, i dołącza do niej miasto 2 (zostają 3). W przypadku miast 3 i 4 nad przekątną nie ma wartości 1, więc odpowiedź wynosi 3.

Struktura union-find, nazywana też strukturą zbiorów rozłącznych, przechowuje każdą grupę jako drzewo. parent[c] wskazuje rodzica o jeden poziom wyżej, a miasto na szczycie, którego rodzicem jest ono samo, jest korzeniem grupy. Dwa miasta należą do tej samej grupy wtedy i tylko wtedy, gdy find prowadzi oba do tego samego korzenia. Aby połączyć dwie grupy, wskaż jeden korzeń jako rodzica drugiego.

Dwie reguły utrzymują płaską strukturę drzew. Łączenie według rangi umieszcza niższe drzewo pod wyższym, dzięki czemu drzewo o wysokości h zawiera co najmniej 2^h miast, a żadna ścieżka nie jest dłuższa niż log n. Kompresja ścieżki idzie o krok dalej: gdy find znajdzie korzeń, wskazuje on bezpośrednio ten korzeń jako rodzica każdego odwiedzonego miasta, więc następne wyszukiwanie rozpoczynane od któregokolwiek z nich wymaga tylko jednego kroku. Bez żadnej z tych reguł łączenie miast w długi łańcuch w niekorzystnej kolejności tworzy drzewo będące pojedynczą ścieżką, a każde find wymaga O(n) kroków.

Przy zastosowaniu obu reguł koszt każdego find wynosi zamortyzowane O(α(n)), gdzie α jest odwrotną funkcją Ackermanna, która dla każdego n, jakie może przechowywać komputer, nie przekracza 4. Odczytanie macierzy nadal wymaga O(n²), więc jest to całkowity koszt, a tablice rodziców i rang zajmują O(n) miejsca. Struktura ta jest przydatna, gdy drogi pojawiają się pojedynczo: po każdej nowej drodze pozwala aktualizować liczbę bez ponownego przeszukiwania.

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 funkcji find przejdź w górę do korzenia, a następnie ponownie przejdź tę samą ścieżkę i skieruj każde miasto na niej bezpośrednio do korzenia.
Jeśli korzenie są różne, dołącz korzeń o niższej randze pod drugi korzeń, przy remisie zwiększ rangę o 1, a licznik zmniejsz 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

Większość błędnych odpowiedzi traktuje 0 jako dowód, że dwa miasta nie są połączone, albo zlicza coś innego niż składowe.

Sprawdzanie tylko bezpośrednich dróg. Miasta 0 i 2 w drugim przykładzie mają między sobą 0, a mimo to należą do tej samej prowincji przez miasto 1. Każde zliczanie oparte wyłącznie na bezpośrednich drogach tego nie uwzględnia; na przykład zliczenie różnych wierszy daje tam 5 zamiast 3.
Zliczanie jedynek i dzielenie przez dwa. W ten sposób zlicza się drogi, a nie prowincje: trzy miasta, z których każde jest połączone z pozostałymi, mają trzy drogi i jedną prowincję.
W strukturze union-find zmniejszanie licznika przy każdej jedynce, zamiast tylko wtedy, gdy korzenie są różne. Droga wewnątrz grupy, która została już scalona, nie może zmieniać licznika.
Porównywanie rodziców zamiast korzeni. parent[i] == parent[j] może być fałszywe dla dwóch miast z tej samej grupy, gdy jedno znajduje się głębiej w drzewie; zawsze porównuj find(i) z find(j).
Dołączanie samego miasta j zamiast jego korzenia, jak w parent[j] = find(i). Jeśli j należało już do grupy, pozostała część tej grupy zostaje odcięta od scalania.
Rekurencja w dużych grafach. Rekurencyjne przeszukiwanie lub rekurencyjne find bez łączenia według rangi przechodzi o jeden poziom na każde miasto w grafie o kształcie łańcucha. To nie problem przy 150 miastach, ale przy 10^5 grozi przepełnieniem stosu.

Najczęstsze pytania4

Jaka jest złożoność czasowa problemu „Liczba prowincji”?

O(n²) zarówno w przypadku przeszukiwania grafu, jak i struktury union-find, ponieważ oba rozwiązania odczytują każdy element macierzy n × n jeden raz. Struktura union-find dodaje czynnik α(n), odwrotną funkcję Ackermanna, która dla każdego rzeczywistego argumentu jest co najwyżej równa 4. Dodatkowe miejsce wynosi O(n) na flagi odwiedzenia albo na tablice rodziców i rang.

Czy do zadania Number of Provinces użyć DFS, BFS czy union-find?

Wszystkie trzy zwracają tę samą liczbę w czasie O(n²). DFS lub BFS najłatwiej napisać, gdy cała macierz jest dostępna od razu. Union-find jest lepszym narzędziem, gdy drogi pojawiają się pojedynczo albo gdy trzeba również odpowiedzieć na pytanie, czy dwa miasta należą do tej samej prowincji, ponieważ obsługuje każdą drogę i każde pytanie w niemal stałym czasie, bez konieczności ponownego wyszukiwania.

Co robią kompresja ścieżki i łączenie według rangi w strukturze union-find?

Łączenie według rangi dołącza krótsze drzewo pod wyższym, gdy dwie grupy są łączone, dzięki czemu każde drzewo ma wysokość co najwyżej log n. Kompresja ścieżek sprawia, że każdy węzeł, przez który przechodzi find, wskazuje bezpośrednio na korzeń, więc późniejsze wyszukiwania rozpoczynające się w tych węzłach wymagają jednego kroku. Przy zastosowaniu obu metod dowolna sekwencja m operacji kosztuje O(m α(n)), co zachowuje się jak czas liniowy.

Jaka jest różnica między liczbą prowincji a liczbą wysp?

Oba rozwiązania liczą spójne składowe. W zadaniu Number of Islands graf ma postać siatki, każde pole ma najwyżej czterech sąsiadów, a złożoność wynosi O(rows × cols). Tutaj graf jest przedstawiony w postaci macierzy sąsiedztwa: każde miasto może być połączone z dowolnym innym, a żeby wypisać sąsiadów jednego miasta, odczytujesz cały wiersz zawierający n wpisów.

Python

def findCircleNum(isConnected):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Wejście

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

Oczekiwane