Hitung Komponen Terhubung
Pelajaran 13 dari 14 dalam kursus Graf, Seri Struktur Data #9 di Coddy.
Komponen terhubung adalah himpunan vertex maksimal sehingga setiap pasang vertex memiliki jalur di antaranya. Graph tanpa edge memiliki jumlah komponen sebanyak jumlah vertex-nya, sedangkan graph yang terhubung sepenuhnya memiliki tepat satu komponen.
Untuk menghitungnya, telusuri semua vertex. Setiap kali kamu menemukan vertex yang belum dikunjungi, itu adalah komponen baru: tambahkan penghitung, lalu lakukan BFS atau DFS dari vertex tersebut untuk menandai semua vertex yang dapat dijangkau sebagai telah dikunjungi. Lanjutkan dengan vertex berikutnya yang belum dikunjungi.
Tantangan ini memberikan DAFTAR vertex dan edge, karena vertex terisolasi (tanpa edge) tetap dihitung sebagai komponen tersendiri dan kita perlu mengetahui bahwa vertex tersebut ada.
Tantangan
MudahTulis fungsi countConnectedComponents yang menerima array int 2D adjacency dan array int vertices, lalu mengembalikan jumlah komponen terhubung dalam graf.
Bangun graf: pertama, panggil addVertex untuk setiap key dalam vertices agar simpul yang terisolasi tetap ada, lalu panggil addEdge untuk setiap pasangan dalam adjacency. Kemudian telusuri semua simpul: setiap simpul yang belum dikunjungi memulai komponen baru, yaitu dengan menambah penghitung, lalu lakukan DFS/BFS dari simpul tersebut untuk menandai seluruh komponennya sebagai sudah dikunjungi.
Kamu harus menggunakan class Graph (disediakan dalam graph), jangan gunakan fitur bawaan bahasa (maps, sets) untuk merepresentasikan adjacency. Data tambahan untuk algoritma (visited sets, stacks) boleh menggunakan tipe dari stdlib.
Coba sendiri
#include <stdio.h>
#include "solution.h"
int main() {
int n, m;
if (scanf("%d %d", &n, &m) != 2) return 0;
int vertices[MAX_VERTICES];
for (int i = 0; i < n; i++) scanf("%d", &vertices[i]);
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%d\n", countConnectedComponents(adjacency, m, vertices, n));
return 0;
}
Semua pelajaran di Graf, Seri Struktur Data #9
Latihan sendiri: Compiler C online