0Pricing
Competitive Programming Academy · Pelajaran

Komponen Terhubung & Flood Fill

Menghitung pulau dan memberi label pada wilayah

Komponen Terhubung & Flood Fill adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.

Apa Itu Komponen

Komponen terhubung adalah kelompok simpul yang semuanya dapat saling mencapai. Sebuah graf dapat memiliki beberapa kelompok yang terpisah. 🧩

Menghitung Komponen

Untuk menghitung komponen, lakukan penelusuran dari setiap simpul yang belum dikunjungi. Setiap titik awal baru menandai satu kelompok baru secara keseluruhan.

Melakukan Perulangan pada Semua Simpul

Telusuri simpul dari 1 hingga n. Saat menemukan simpul yang masih belum dikunjungi, Anda telah menemukan komponen baru untuk dijelajahi.

for s in range(1, n + 1):
    if not visited[s]:
        bfs_or_dfs(s)
        count += 1

Satu Penelusuran per Kelompok

BFS atau DFS bagian dalam tersebut menandai seluruh komponen sebagai telah dikunjungi, sehingga perulangan luar melewatinya pada putaran berikutnya.

Kisi Juga Merupakan Graf

Kisi 2D adalah graf tersembunyi: setiap sel merupakan simpul yang terhubung dengan tetangganya. Ini membuka gagasan klasik pengisian area. 🗺️

Empat Arah

Dari sebuah sel, Anda biasanya bergerak ke atas, bawah, kiri, dan kanan. Simpan gerakan tersebut sebagai vektor arah agar kode tetap rapi.

dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

Tetap di Dalam Kisi

Sebelum melangkah, periksa apakah baris dan kolom baru berada dalam batas. Melewatkan pemeriksaan ini dapat menyebabkan kesalahan indeks atau jawaban yang salah.

if 0 <= nr < rows and 0 <= nc < cols:
    pass

Mengisi Satu Area

Pengisian area dimulai dari sebuah sel dan menyebar ke setiap sel terhubung yang memiliki jenis sama, seperti alat ember cat.

Menghitung Pulau

Untuk menghitung pulau, telusuri kisi; pada setiap sel daratan baru, isi seluruh pulaunya lalu tambahkan satu ke jumlahnya.

if grid[r][c] == '1' and not seen[r][c]:
    flood(r, c)
    islands += 1

Memberi Label pada Wilayah

Anda dapat menyimpan label untuk setiap sel selama proses pengisian. Setelah itu, Anda dapat langsung mengetahui wilayah tempat sel mana pun berada.

Linear terhadap Ukuran Kisi

Setiap sel dikunjungi sekali, sehingga pengisian area pada kisi berjalan dalam O(rows kali cols). Kompleksitas ini dengan mudah memenuhi batas kontes.

Pemeriksaan Singkat

Bagaimana cara menghitung komponen terhubung?

Rekapitulasi

Anda menghitung komponen dengan menelusuri dari setiap simpul yang belum dikunjungi, lalu menggunakan pengisian area pada kisi untuk memberi label wilayah dan menghitung pulau. 🎉

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Komponen Terhubung & Flood Fill” gratis?

Ya — teks lengkap “Komponen Terhubung & Flood Fill” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Competitive Programming Academy, upgrade ke CoddyKit PRO. Kursus Competitive Programming Academy mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Komponen Terhubung & Flood Fill”?

Menghitung pulau dan memberi label pada wilayah Kamu berlatih Competitive Programming Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai Competitive Programming Academy?

Tidak diperlukan pengalaman sebelumnya. Competitive Programming Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.

Berapa lama pelajaran “Komponen Terhubung & Flood Fill” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran Competitive Programming Academy ini?

Ya. Setiap pelajaran Competitive Programming Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

  1. Adjacency List dari Input
  2. BFS untuk Jalur Terpendek Tanpa Bobot
  3. DFS, Rekursi & Stack Iteratif
  4. Komponen Terhubung & Flood Fill
← Kembali ke Competitive Programming Academy