المكوّنات المتصلة والملء الانتشاري
عدّ الجزر ووضع علامات على المناطق
المكوّنات المتصلة والملء الانتشاري درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 4 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ما هو المكوّن
المكوّن المتصل هو مجموعة من العقد يمكن الوصول من كل واحدة منها إلى جميع العقد الأخرى. وقد يحتوي الرسم البياني على عدة مجموعات منفصلة. 🧩
عدّ المكوّنات
لعدّ المكوّنات، نفّذ عملية اجتياز بدءًا من كل عقدة لم تتم زيارتها. وكل بداية جديدة تمثّل مجموعة جديدة كاملة.
التكرار على جميع العقد
مرّر على العقد من 1 إلى n. عندما تجد عقدة لم تتم زيارتها بعد، تكون قد اكتشفت مكوّنًا جديدًا لاستكشافه.
for s in range(1, n + 1):
if not visited[s]:
bfs_or_dfs(s)
count += 1عملية اجتياز واحدة لكل مجموعة
تضع عملية BFS أو DFS الداخلية علامة الزيارة على المكوّن بأكمله، لذلك تتجاوزه الحلقة الخارجية في المرة التالية.
الشبكات أيضًا رسوم بيانية
الشبكة ثنائية الأبعاد رسم بياني مخفي: كل خلية عقدة متصلة بجيرانها. وهذا يفتح المجال أمام فكرة الملء الانتشاري المعروفة. 🗺️
الاتجاهات الأربعة
تتحرك عادةً من الخلية إلى الأعلى والأسفل واليسار واليمين. خزّن هذه الحركات في متجهات الاتجاه للحفاظ على نظافة الشيفرة.
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]ابقَ داخل الشبكة
قبل الانتقال، تحقّق من أن الصف والعمود الجديدين يقعان ضمن الحدود. يؤدي تجاهل هذا التحقق إلى أخطاء الفهارس أو إلى إجابات خاطئة.
if 0 <= nr < rows and 0 <= nc < cols:
passاملأ منطقة واحدة
يبدأ الملء الغمري من خلية وينتشر إلى كل خلية متصلة من النوع نفسه، تمامًا مثل أداة دلو الطلاء.
عدّ الجزر
لعدّ الجزر، امسح الشبكة؛ وعند كل خلية برية جديدة، نفّذ ملءً غمريًا للجزيرة بأكملها وأضف واحدًا إلى العدد.
if grid[r][c] == '1' and not seen[r][c]:
flood(r, c)
islands += 1وسم المناطق
يمكنك تخزين وسم لكل خلية أثناء الملء. وبعد ذلك ستعرف فورًا إلى أي منطقة تنتمي كل خلية.
خطي بالنسبة إلى حجم الشبكة
تتم زيارة كل خلية مرة واحدة، لذلك يعمل الملء الغمري على شبكة في O(عدد الصفوف × عدد الأعمدة). وهذا يفي بحدود مسائل المسابقات بسهولة.
اختبار سريع
كيف تعدّ المكوّنات المتصلة؟
مراجعة
تعدّ المكوّنات من خلال الاجتياز بدءًا من كل عقدة لم تُزَر، وتستخدم الملء الغمري على الشبكات لوَسم المناطق وعدّ الجزر. 🎉
الأسئلة الشائعة
هل درس «المكوّنات المتصلة والملء الانتشاري» مجاني؟
نعم — نص درس «المكوّنات المتصلة والملء الانتشاري» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «المكوّنات المتصلة والملء الانتشاري»؟
عدّ الجزر ووضع علامات على المناطق تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 4 من أصل 4.
كم من الوقت يستغرق درس «المكوّنات المتصلة والملء الانتشاري»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- قوائم التجاور من الإدخال
- BFS لأقصر المسارات غير الموزونة
- DFS والاستدعاء الذاتي والمكدسات التكرارية
- المكوّنات المتصلة والملء الانتشاري