Spójne składowe i flood fill
Zliczanie wysp i oznaczanie regionów
Spójne składowe i flood fill to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 4 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 jest składowa
Spójna składowa to grupa wierzchołków, z których każdy można osiągnąć z każdego innego. Graf może zawierać kilka oddzielnych grup. 🧩
Zliczanie składowych
Aby policzyć składowe, należy uruchomić przeszukiwanie z każdego nieodwiedzonego wierzchołka. Każdy nowy punkt startowy oznacza odkrycie całej nowej grupy.
Przechodzenie po wszystkich wierzchołkach
Należy przejść po wierzchołkach od 1 do n. Gdy znaleziony zostanie wciąż nieodwiedzony wierzchołek, oznacza to odkrycie nowej składowej do zbadania.
for s in range(1, n + 1):
if not visited[s]:
bfs_or_dfs(s)
count += 1Jedno przeszukiwanie na grupę
Wewnętrzne przeszukiwanie BFS lub DFS oznacza całą składową jako odwiedzoną, dzięki czemu zewnętrzna pętla pomija ją przy kolejnym przejściu.
Siatki również są grafami
Siatka 2D to ukryty graf: każda komórka jest wierzchołkiem połączonym z sąsiadami. Otwiera to drogę do klasycznej koncepcji wypełniania obszaru. 🗺️
Cztery kierunki
Z komórki zwykle można przejść w górę, w dół, w lewo i w prawo. Warto przechowywać te ruchy jako wektory kierunków, aby zachować przejrzystość kodu.
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]Pozostawanie w granicach siatki
Przed wykonaniem ruchu należy sprawdzić, czy nowy wiersz i kolumna mieszczą się w granicach. Pominięcie tego sprawdzenia prowadzi do błędów indeksowania lub niepoprawnych odpowiedzi.
if 0 <= nr < rows and 0 <= nc < cols:
passWypełnianie jednego obszaru
Flood fill rozpoczyna się w jednej komórce i rozprzestrzenia na wszystkie połączone komórki tego samego typu, podobnie jak narzędzie wiadra z farbą.
Zliczanie wysp
Aby zliczyć wyspy, należy przejść przez siatkę; przy każdej nowej komórce lądu wykonuje się flood fill dla całej wyspy i zwiększa licznik o jeden.
if grid[r][c] == '1' and not seen[r][c]:
flood(r, c)
islands += 1Etykietowanie obszarów
Podczas wypełniania można przechowywać etykietę dla każdej komórki. Później od razu wiadomo, do którego obszaru należy dowolna komórka.
Liniowa względem rozmiaru siatki
Każda komórka jest odwiedzana raz, więc flood fill dla siatki działa w czasie O(liczba wierszy razy liczba kolumn). Taka złożoność bez problemu mieści się w limitach zadań konkursowych.
Krótki test
Jak zlicza się spójne składowe?
Podsumowanie
Składowe zlicza się, przechodząc od każdego nieodwiedzonego wierzchołka, a na siatkach używa się flood fill do etykietowania obszarów i zliczania wysp. 🎉
Ucz się Coding Interview Prep dzięki korepetycjom AI — za darmo
Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.
- Kursy
- 90
- Lekcje
- 360
Często zadawane pytania
Czy lekcja „Spójne składowe i flood fill” jest bezpłatna?
Tak — pełny tekst „Spójne składowe i flood fill” 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 „Spójne składowe i flood fill”?
Zliczanie wysp i oznaczanie regionów Ć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 4 z 4.
Ile czasu zajmuje lekcja „Spójne składowe i flood fill”?
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
- Listy sąsiedztwa z danych wejściowych
- BFS dla najkrótszych ścieżek nieważonych
- DFS, rekurencja i stosy iteracyjne
- Spójne składowe i flood fill