Graph Valid Tree

+10

Otrzymujesz n węzłów ponumerowanych od 0 do n-1 oraz listę edges zawierającą nieskierowane krawędzie. Każda para [a, b] łączy węzeł a z węzłem b.

Zwróć true, jeśli krawędzie tworzą jedno drzewo obejmujące wszystkie n węzłów: każdy węzeł może dotrzeć do każdego innego i nie ma żadnego cyklu. W przeciwnym razie zwróć false.

Funkcja

validTree(n: integer, edges: integer-2d-array) → boolean

ninteger: liczba węzłów, ponumerowanych od 0 do n-1
edgesinteger-2d-array: nieskierowane krawędzie, każda w postaci pary [a, b]
Zwracaboolean: true, jeśli krawędzie łączą wszystkie n węzłów w jedno drzewo, w przeciwnym razie false

Ograniczenia

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [a, b], gdzie 0 ≤ a, b ≤ n-1 i a ≠ b
Żadna krawędź nie występuje dwukrotnie, w żadnym kierunku.

Przykłady

Wejście: n = 5edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
Wyjście: true
Wyjaśnienie: Węzeł 0 łączy się z węzłami 1, 2 i 3, a węzeł 4 odchodzi od węzła 1. Cztery krawędzie łączą wszystkie pięć węzłów i nie tworzą żadnej pętli, więc jest to drzewo.

Wejście: n = 5edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
Wyjście: false
Wyjaśnienie: Krawędzie [1, 2], [2, 3] i [1, 3] tworzą pętlę 1, 2, 3, 1. Pięć krawędzi w pięciu węzłach to o jedną więcej, niż może mieć drzewo.

Wejście: n = 4edges = [[0, 1], [1, 2], [2, 0]]
Wyjście: false
Wyjaśnienie: Są 3 krawędzie, czyli n-1, ale tworzą one pętlę 0, 1, 2, 0, a węzeł 3 nie ma żadnej krawędzi.

Pytanie dodatkowe

Jeśli graf nie jest drzewem, ile krawędzi trzeba usunąć i ile dodać, aby stał się drzewem? Czy potrafisz policzyć obie liczby w jednym przebiegu?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Drzewo jest spójne i nie ma cykli. Przy dokładnie n-1 krawędziach te warunki są równoważne: taki graf jest spójny wtedy i tylko wtedy, gdy nie ma cykli. Najpierw sprawdź więc liczbę krawędzi, a następnie albo raz sprawdź spójność, albo pozwól strukturze union-find wykryć krawędź łączącą dwa węzły, które są już połączone.

Szukaj ścieżki przed każdą krawędzią

Poprawne, ale nie kończy się na największych testach

Intuicja

Dodawaj krawędzie po jednej. Przed dodaniem [u, v] przeszukaj graf od u, korzystając z dotychczas dodanych krawędzi. Jeśli można dotrzeć do v, nowa krawędź tworzy drugą drogę między nimi i zamyka cykl, tak jak robi to [1, 3] w drugim przykładzie. Jeśli żadna krawędź nie zamyka cyklu, graf jest lasem, a ostatnie przeszukiwanie od wierzchołka 0 pozwala sprawdzić, czy jest jednym drzewem.

Każde sprawdzenie przeszukuje cały dotychczasowy graf. Na ścieżce składającej się z 5001 wierzchołków, której krawędzie są dodawane po kolei, przeszukiwania odwiedzają 1 + 2 + ... + 5000 wierzchołków, czyli około 12,5 miliona.

Algorytm

Zacznij od pustej listy sąsiedztwa dla każdego węzła.
Dla każdej krawędzi [u, v] przeszukaj graf od u, korzystając z dotychczas dodanych krawędzi. Jeśli dotrze do v, zwróć false.
W przeciwnym razie dodaj krawędź do list obu jej końców.
Na końcu zwróć informację, czy przeszukiwanie od węzła 0 dociera do wszystkich n węzłów.

def reachable(graph, start):
    # Every node a search from start can reach, using the edges added so far.
    seen = [False] * len(graph)
    seen[start] = True
    stack = [start]
    while stack:
        node = stack.pop()
        for nxt in graph[node]:
            if not seen[nxt]:
                seen[nxt] = True
                stack.append(nxt)
    return seen


def validTree(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        # A path from u to v already exists, so this edge closes a cycle.
        if reachable(graph, u)[v]:
            return False
        graph[u].append(v)
        graph[v].append(u)
    # No cycle anywhere. A tree also needs every node reachable from node 0.
    return all(reachable(graph, 0))

Policz krawędzie, a następnie wyszukaj raz

Intuicja

Zacznij od n oddzielnych węzłów i dodawaj krawędzie pojedynczo. Każda krawędź albo łączy dwie grupy, zmniejszając ich liczbę o jeden, albo trafia do wnętrza grupy i zamyka cykl. Połączenie wszystkich w jedną grupę wymaga n-1 połączeń. Zatem mniej niż n-1 krawędzi nie wystarczy, by połączyć graf, a większa liczba musi zamknąć cykl: drugi przykład, 5 krawędzi na 5 węzłach, nie spełnia warunku już ze względu na samą liczbę krawędzi.

Przy dokładnie n-1 krawędziach graf kończy jako jedna grupa tylko wtedy, gdy każda krawędź była połączeniem, czyli tylko jeśli żadna krawędź nie zamknęła cyklu. Gdy liczba krawędzi jest prawidłowa, sprawdź więc samo spójność: jedno przeszukiwanie od węzła 0 musi dotrzeć do wszystkich n węzłów. W trzecim przykładzie dociera tylko do węzłów 0, 1 i 2. Dla m = n-1 listy i przeszukiwanie mają koszt O(n).

Algorytm

Jeśli edges.length nie jest równe n-1, zwróć false.
Zbuduj listę sąsiedztwa, zapisując każdą krawędź przy obu jej końcach.
Umieść węzeł 0 na stosie i oznacz go jako odwiedzony.
Zdejmuj węzły ze stosu i dodawaj każdego jeszcze nieodwiedzonego sąsiada, oznaczając go i zwiększając licznik w chwili dodawania.
Zwróć informację, czy licznik jest równy n.

def validTree(n, edges):
    # A tree on n nodes has exactly n-1 edges.
    if len(edges) != n - 1:
        return False
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    # With n-1 edges, the graph is a tree exactly when it is connected.
    seen = [False] * n
    seen[0] = True
    stack = [0]
    reached = 1
    while stack:
        node = stack.pop()
        for nxt in graph[node]:
            if not seen[nxt]:
                seen[nxt] = True
                reached += 1
                stack.append(nxt)
    return reached == n

Policz krawędzie i użyj struktury union-find

Intuicja

Struktura union-find odpowiada na pytanie o cykl dla każdej krawędzi bez wyszukiwania. Każdy wierzchołek początkowo należy do własnej grupy. Dla krawędzi [u, v] znajdź korzeń każdego z jej końców. Różne korzenie: krawędź łączy dwie części, więc połącz je. Ten sam korzeń: u i v są już połączone, a krawędź zamyka cykl. Jeśli wszystkie n-1 krawędzi łączą grupy, n grup ostatecznie połączy się w jedną: drzewo.

Dwie zasady utrzymują krótkie łańcuchy rodziców. Podczas łączenia korzeń mniejszej grupy zostaje podpięty pod korzeń większej, więc przy 10^4 wierzchołkach żaden łańcuch nie przekracza 13 kroków. Podczas wyszukiwania ustaw rodzica każdego odwiedzanego wierzchołka na jego dziadka. Łącznie sprawiają, że m operacji kosztuje O(m α(n)), gdzie α, odwrotna funkcja Ackermanna, wynosi tutaj najwyżej 4. Złożoność pamięciowa to O(n).

Algorytm

Jeśli edges.length nie jest równe n-1, zwróć false.
Ustaw parent[x] = x i rozmiar każdej grupy na 1 dla każdego węzła.
Dla każdej krawędzi [u, v] przejdź po rodzicach od u i od v aż do ich korzeni, wskazując każdego odwiedzanego węzła na jego dziadka.
Równe korzenie: zwróć false.
Różne korzenie: dołącz korzeń mniejszej grupy do drugiego i dodaj rozmiar tej grupy.
Jeśli każda krawędź połączyła dwie grupy, zwróć true.

def validTree(n, edges):
    # A tree on n nodes has exactly n-1 edges.
    if len(edges) != n - 1:
        return False
    parent = list(range(n))  # every node starts as its own group
    size = [1] * n

    def find(x):
        # Walk up to the root, halving the path on the way.
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for u, v in edges:
        a, b = find(u), find(v)
        # The two ends are already joined: this edge closes a cycle.
        if a == b:
            return False
        # Hang the smaller group under the larger one.
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]
    # n-1 merges with no cycle turn the n groups into one.
    return True

Pułapki i przypadki brzegowe

Sprawdzanie tylko, czy występuje cykl. Trzy osobne krawędzie łączące sześć wierzchołków nie tworzą cyklu, a mimo to tworzą trzy składowe.
Sprawdzanie tylko liczby krawędzi. Trzeci przykład ma n-1 krawędzi, ale pętla 0, 1, 2 zużywa krawędź z wierzchołkiem 3, która jest potrzebna.
Przechowywanie każdej krawędzi tylko przy jednym jej końcu. [1, 0] również łączy wierzchołki 0 i 1, a wyszukiwanie od wierzchołka 0 nie znajduje wierzchołka 1.
Testowanie cyklu metodą przeszukiwania w głąb bez pomijania rodzica. Każda krawędź prowadzi prosto z powrotem do wierzchołka, z którego przyszliśmy, więc warunek „napotkano odwiedzonego sąsiada” uruchamia się w każdym drzewie.
Rekurencyjne przechodzenie długiej ścieżki. Ścieżka z 5001 wierzchołkami oznacza 5000 wywołań w głąb, co przekracza domyślny limit Pythona wynoszący 1000; użyj jawnego stosu.

Najczęstsze pytania3

Jaka jest złożoność czasowa algorytmu sprawdzającego, czy graf jest drzewem?

O(n + m) przy użyciu przeszukiwania w głąb i O(n + m α(n)) przy użyciu struktury union-find. Oba rozwiązania najpierw sprawdzają liczbę krawędzi, więc graf o nieprawidłowej liczbie krawędzi zostaje odrzucony przed rozpoczęciem wyszukiwania.

Dlaczego drzewo z n węzłami ma n-1 krawędzi?

Rozbuduj drzewo, zaczynając od jednego węzła, i dodawaj pozostałe po jednym. Każdy nowy węzeł pojawia się z dokładnie jedną krawędzią: bez żadnej zostałby odcięty, a z dwiema zamknąłby cykl. Zatem n węzłów potrzebuje n-1 krawędzi.

Jak wykryć cykl w grafie nieskierowanym?

W strukturze union-find krawędź, której oba końce mają już wspólny korzeń, zamyka cykl. W przeszukiwaniu w głąb cyklem jest odwiedzony sąsiad inny niż węzeł, z którego dotarłeś, więc śledzisz rodzica każdego węzła. Struktura union-find nie wymaga ani rodzica, ani listy sąsiedztwa.

def validTree(n, edges):
    # Wpisz tutaj kod

Test #1

Test #2

Test #3

Argumenty

n = 5
edges = [[0, 1], [0, 2], [0, 3], [1, 4]]

Oczekiwany wynik

true

Graph Valid Tree

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Szukaj ścieżki przed każdą krawędzią

Policz krawędzie, a następnie wyszukaj raz

Policz krawędzie i użyj struktury union-find

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania