Implementation (Part 1)
الدرس 5 من 9 في دورة خوارزمية كروسكال - خوارزميات الرسوم البيانية على Coddy.
نبدأ بخوارزمية union-find، وهي محرك كشف الدورات.
التحدي
متوسطيعتمد اختبار الدورة في خوارزمية Kruskal على union-find. لنقم ببناء ذلك أولاً، واستخدامه لحساب المكونات المتصلة (connected components).
اكتب دالة باسم countSets تأخذ n ومصفوفة edges المسطحة (ثلاثيات [u, v, w, ...]، غير موجهة؛ تجاهل الأوزان هنا) وتُرجع عدد المكونات المتصلة، المحسوبة باستخدام union-find.
على سبيل المثال، مع 4 رؤوس وحواف [0,1,5, 2,3,5] هناك مكونان: {0,1} و {2,3}.
جرّب بنفسك
#include <stdlib.h>
int countSets(int n, int* edges, int edges_size) {
// اكتب الكود هنا
return 0;
}
اختبر نفسكيتضمن هذا الدرس اختبارًا قصيرًا. ابدأ الدرس للإجابة عليه وتتبّع تقدمك.
جميع دروس خوارزمية كروسكال - خوارزميات الرسوم البيانية
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity