Bağlı Bileşenleri Sayma
Coddy'nin Graflar - Veri Yapıları Serisi #9 kursunda ders 13 / 14.
Bir bağlı bileşen (connected component), her düğüm çifti arasında bir yolun bulunduğu maksimal bir düğüm kümesidir. Hiç kenarı olmayan bir graf, düğüm sayısı kadar bileşene sahiptir; tam bağlı bir graf ise tam olarak bir bileşene sahiptir.
Bunları saymak için tüm düğümleri dolaşın. Henüz ziyaret edilmemiş bir düğüm bulduğunuzda, bu yeni bir bileşendir: sayacı artırın, ardından ulaşılabilir her düğümü ziyaret edildi olarak işaretlemek için oradan BFS veya DFS başlatın. Bir sonraki ziyaret edilmemiş düğümle devam edin.
Bu görev size HEM düğüm listesini HEM DE kenarları verir, çünkü izole edilmiş düğümler (kenarı olmayanlar) hala kendi başlarına bir bileşen sayılırlar ve onların var olduğunu bilmemiz gerekir.
Görev
KolayBir 2D tam sayı dizisi adjacency ve bir tam sayı dizisi vertices alan ve grafikteki bağlı bileşenlerin sayısını döndüren bir countConnectedComponents fonksiyonu yazın.
Grafı oluşturun: önce vertices içindeki her anahtar üzerinde addVertex işlemini gerçekleştirin (böylece izole edilmiş düğümler de mevcut olur), ardından adjacency içindeki her çift üzerinde addEdge işlemini yapın. Sonra tüm düğümleri gezin: ziyaret edilmemiş her bir düğüm yeni bir bileşen başlatır (sayacı artırın), ardından o bileşenin tamamını ziyaret edildi olarak işaretlemek için o düğümden DFS/BFS başlatın.
Graph sınıfını kullanmalısınız (graph içinde sağlanmıştır) - komşuluk yapısını modellemek için dilin yerleşik yapılarını (map'ler, set'ler) kullanmayın. Algoritma için yardımcı veriler (ziyaret edilen setleri, yığınlar) standart kütüphane tiplerini kullanabilir.
Kendin dene
#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;
}