0Pricing
Coding Interview Prep · Lekcja

Listy sąsiedztwa z danych wejściowych

Budowanie grafu otrzymywanego w zadaniach konkursowych

Listy sąsiedztwa z danych wejściowych to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Czym naprawdę jest graf

Graf to po prostu punkty nazywane wierzchołkami, połączone liniami nazywanymi krawędziami. Miasta połączone drogami tworzą znany już Państwu przykład grafu. 🗺️

Wierzchołki i krawędzie

Każdy wierzchołek reprezentuje pewien obiekt, a każda krawędź oznacza połączenie dwóch wierzchołków. W grafach konkursowych wierzchołki zwykle numeruje się od 1 do n.

Lista sąsiedztwa

Najczęściej używaną w zadaniach konkursowych strukturą przechowywania grafu jest lista sąsiedztwa: dla każdego wierzchołka przechowuje się listę jego bezpośrednich sąsiadów.

adj = [[] for _ in range(n + 1)]

Dlaczego nie macierz

Macierz wymaga n do kwadratu pamięci, co przy dużym n szybko staje się problemem. Lista sąsiedztwa przechowuje tylko istniejące krawędzie, dzięki czemu lepiej się skaluje.

Odczytywanie pierwszego wiersza

Większość danych wejściowych zaczyna się od dwóch liczb: n wierzchołków i m krawędzi. Należy odczytać je najpierw, aby wiedzieć, ilu krawędzi się spodziewać.

n, m = map(int, input().split())

Jedna krawędź w każdym wierszu

Każdy z kolejnych m wierszy zawiera parę u v. Ta pojedyncza krawędź oznacza, że u i v są bezpośrednio połączone.

u, v = map(int, input().split())

Nieskierowany oznacza oba kierunki

W przypadku krawędzi nieskierowanej należy dodać połączenie w obu kierunkach. Można przejść z u do v oraz z v do u.

adj[u].append(v)
adj[v].append(u)

Skierowany oznacza jeden kierunek

W przypadku krawędzi skierowanej należy przechowywać tylko połączenie z u do v. Proszę uważnie czytać treść zadania, aby rozpoznać rodzaj grafu.

adj[u].append(v)

Budowanie grafu w pętli

Należy wykonać pętlę m razy, odczytać każdą parę i uzupełnić listy. Po zakończeniu pętli lista sąsiedztwa zawiera cały graf.

for _ in range(m):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)

Indeksowanie od 1 a od 0

Jeśli wierzchołki zaczynają się od 1, listę należy utworzyć w rozmiarze n plus 1, aby indeks n był poprawny. Pomylenie sposobu indeksowania powoduje trudne do wykrycia błędy.

Odwiedzanie sąsiadów wierzchołka

Po zbudowaniu grafu eksploracja jest prosta: należy przejść pętlą po adj danego wierzchołka, aby w jednym kroku dotrzeć do każdego sąsiada.

for nb in adj[u]:
    print(nb)

Szybkie sprawdzenie

Odczytano nieskierowaną krawędź u v. Co należy przechowywać?

Podsumowanie

Graf można teraz budować jako listę sąsiedztwa: odczytać n i m, przejść po krawędziach oraz dodać oba kierunki, gdy graf jest nieskierowany. 🎉

Często zadawane pytania

Czy lekcja „Listy sąsiedztwa z danych wejściowych” jest bezpłatna?

Tak — pełny tekst „Listy sąsiedztwa z danych wejściowych” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Co nauczysz się w „Listy sąsiedztwa z danych wejściowych”?

Budowanie grafu otrzymywanego w zadaniach konkursowych Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?

Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.

Ile czasu zajmuje lekcja „Listy sąsiedztwa z danych wejściowych”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?

Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. Listy sąsiedztwa z danych wejściowych
  2. BFS dla najkrótszych ścieżek nieważonych
  3. DFS, rekurencja i stosy iteracyjne
  4. Spójne składowe i flood fill
← Powrót do Coding Interview Prep