Spójne składowe i flood fill
Zliczanie wysp i oznaczanie regionów
Spójne składowe i flood fill to bezpłatna lekcja Competitive Programming Academy 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 Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy 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. 🎉
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 Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Spójne składowe i flood fill”?
Zliczanie wysp i oznaczanie regionów Ćwiczysz Competitive Programming Academy 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ąć Competitive Programming Academy?
Nie wymagamy żadnego doświadczenia. Competitive Programming Academy 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 Competitive Programming Academy?
Tak. Każda lekcja Competitive Programming Academy 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