DSU مع ضغط المسار
العثور والضم في زمن شبه ثابت
DSU مع ضغط المسار درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 1 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ما الذي يتتبعه DSU
يحافظ Disjoint Set Union على تجميع العناصر في مجموعات غير متداخلة، بحيث يمكنك معرفة ما إذا كان عنصران ينتميان إلى المجموعة نفسها. 🤝
المجموعات على شكل أشجار
يخزّن DSU كل مجموعة على شكل شجرة. يشير كل عنصر إلى أب، وتكون العقدة الأعلى، أي الجذر، الاسم الفريد للمجموعة بأكملها.
مصفوفة الآباء
تحتفظ بكل تلك الروابط في مصفوفة واحدة. ابدأ باعتبار كل عنصر أبًا لنفسه، أي إن كل عنصر يبدأ في مجموعة مستقلة.
parent = list(range(n))العثور على الجذر
تتنقل عملية find صعودًا عبر روابط الآباء حتى يشير عنصر إلى نفسه. هذه العقدة التي تشير إلى نفسها هي الجذر الذي يحدد المجموعة.
while parent[x] != x:
x = parent[x]السلاسل الطويلة تسبب مشكلات
من دون عناية، قد تشكّل المجموعات سلاسل طويلة ورفيعة. عندها تتنقل find عبر العقد واحدة تلو الأخرى، وقد يستغرق الاستعلام الواحد O(n)، وهذا بطيء جدًا.
إدخال ضغط المسار
يحل ضغط المسار هذه المشكلة: أثناء العثور على الجذر، تعيد توجيه كل عقدة زرتها مباشرةً إلى الجذر، فتسطّح الشجرة للاستعمال التالي. ⚡
الضغط التكراري
الطريقة الأنظف هي الاستدعاء التكراري. اعثر على الجذر، ثم خزّنه مرة أخرى في parent[x] قبل العودة، وبذلك تُقصّر الرابط بشكل دائم.
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]عنصران، هل ينتميان إلى المجموعة نفسها؟
للتحقق مما إذا كان عنصران متصلين، قارن جذريهما. إذا كان find(a) equals find(b)، فهما في المجموعة نفسها؛ وإلا فهما لا يزالان منفصلين.
if find(a) == find(b):
print("connected")دمج مجموعتين
تضم عملية union المجموعات بتوجيه أحد الجذرين إلى الآخر. يربط سطر واحد شجرتين كاملتين في مجموعة واحدة.
def union(a, b):
parent[find(a)] = find(b)لماذا هي سريعة جدًا
باستخدام ضغط المسار وحده، تعمل العمليات تقريبًا في O(log n) بالمتوسط التراكمي، ومع دمجه بترتيب الرتب تصل إلى زمن قريب من الثابت لكل استعلام.
حيث يتألق DSU
يشغّل DSU مسائل الاتصال: دوائر الأصدقاء، ومكوّنات الشبكات، وشجرة الامتداد لخوارزمية Kruskal، كلها تعتمد على find وunion السريعتين. 🌐
تحقّق سريع
فكّر في ما الذي يغيّره ضغط المسار فعليًا.
مراجعة
أنشأتَ DSU: مصفوفة آباء، وfind للحصول على الجذر، وunion للدمج. يحافظ ضغط المسار على سرعتها الفائقة. عمل رائع! 🎉
الأسئلة الشائعة
هل درس «DSU مع ضغط المسار» مجاني؟
نعم — نص درس «DSU مع ضغط المسار» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «DSU مع ضغط المسار»؟
العثور والضم في زمن شبه ثابت تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 1 من أصل 4.
كم من الوقت يستغرق درس «DSU مع ضغط المسار»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- DSU مع ضغط المسار
- الضم حسب الرتبة والمكوّنات
- شجرة Kruskal الممتدة الدنيا
- MST لخوارزمية Prim باستخدام كومة