عد المكونات المتصلة
الدرس 13 من 14 في دورة المخططات - سلسلة هياكل البيانات #9 على Coddy.
المكون المتصل (connected component) هو مجموعة قصوى من الرؤوس حيث يوجد مسار بين كل زوج منها. الرسم البياني الذي لا يحتوي على حواف يحتوي على عدد من المكونات يساوي عدد رؤوسه؛ أما الرسم البياني المتصل تمامًا فيحتوي على مكون واحد فقط.
لعدّها، قم بالمرور على جميع الرؤوس. كلما وجدت رأسًا لم يتم زيارته بعد، فهذا يعني وجود مكون جديد: قم بزيادة العداد، ثم ابدأ عملية BFS أو DFS منه لتمييز كل رأس يمكن الوصول إليه كـ "تمت زيارته". استمر مع الرأس التالي غير المزار.
يمنحك هذا التحدي كلاً من قائمة الرؤوس والحواف، لأن الرؤوس المعزولة (التي لا تحتوي على حواف) لا تزال تُحسب كمكون خاص بها ويجب أن نعرف بوجودها.
التحدي
سهلاكتب دالة countConnectedComponents تستقبل مصفوفة أعداد صحيحة ثنائية الأبعاد adjacency ومصفوفة أعداد صحيحة vertices، وتعيد عدد المكونات المتصلة في الرسم البياني.
قم ببناء الرسم البياني: أولاً استدعِ addVertex لكل مفتاح في vertices (بحيث تكون الرؤوس المعزولة موجودة)، ثم استدعِ addEdge لكل زوج في adjacency. ثم مر على جميع الرؤوس: كل رأس غير مزار يبدأ مكوناً جديداً (قم بزيادة العداد)، ثم استخدم DFS/BFS منه لتمييز المكون بالكامل كمزار.
يجب عليك استخدام فئة Graph (المتوفرة في graph) - لا تستخدم الأدوات المدمجة في اللغة (الخرائط، المجموعات) لتمثيل التجاور. البيانات المساعدة للخوارزمية (مجموعات الزيارة، المكدسات) يمكن أن تستخدم أنواع مكتبة المعايير (stdlib).
جرّب بنفسك
#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;
}