هل الرسم ثنائي التجزئة
الدرس 14 من 14 في دورة المخططات - سلسلة هياكل البيانات #9 على Coddy.
يكون الرسم البياني ثنائي التجزئة (bipartite) إذا كان بإمكانك تقسيم رؤوسه إلى مجموعتين بحيث يربط كل ضلع بين رأس في مجموعة واحدة ورأس في المجموعة الأخرى. تخيل اللونين الأحمر والأزرق: كل ضلع له طرف أحمر وطرف أزرق.
يوفر خوارزمية البحث بالعرض أولاً (BFS) اختباراً واضحاً. ابدأ من أي رأس، ولونه بالأحمر، ثم تحرك نحو الخارج. يحصل كل جار جديد على اللون المعاكس للرأس الذي جئنا منه. إذا رأينا ضلعاً يربط بين رأسين لهما نفس اللون، فإن الرسم البياني ليس ثنائي التجزئة. المسبب الكلاسيكي لهذه المشكلة هو دورة ذات طول فردي: فالمثلث 0-1-2-0 يجبر الرأس 0 على أن يكون أحمر وأزرق في نفس الوقت.
شيء واحد يجب تذكره: إذا كان الرسم البياني يحتوي على عدة مكونات متصلة، فيجب عليك بدء عملية تلوين ثنائية جديدة لكل منها. أسهل نمط هو حلقة واحدة تمر عبر جميع الرؤوس وتبدأ خوارزمية BFS كلما وجدت رأساً غير ملون.
التحدي
سهلاكتب دالة isBipartite تستقبل مصفوفة ثنائية الأبعاد من الأعداد الصحيحة adjacency ومصفوفة أعداد صحيحة vertices، وتعيد true إذا كان الرسم البياني ثنائي التجزئة (bipartite)، و false بخلاف ذلك.
قم ببناء الرسم البياني (استخدم addVertex لكل رأس، ثم addEdge لكل حافة). بعد ذلك، قم بالتلوين بلونين (2-color) عبر خوارزمية BFS على كل مكون متصل: قم بتعيين اللون الابتدائي 0، وأعطِ كل جار اللون 1 - color[u]. إذا وجدت حافة يكون لكلا طرفيها نفس اللون، فقم بإعادة false. بخلاف ذلك، أعد true.
يجب عليك استخدام فئة Graph (المتوفرة في graph) - لا تستخدم الأدوات المدمجة في اللغة (maps، sets) لتمثيل التجاور. يمكن استخدام أنواع المكتبة القياسية (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("%s\n", isBipartite(adjacency, m, vertices, n) ? "true" : "false");
return 0;
}