هيكل البيانات لفصول التكافؤ

Question

دع $ E $ تكون علاقة التكافؤ المعرفة على مجموعة $ S $ . الوصول إلى $ e $ هو فقط عبر استعلامات النموذج $ m (s_1، s_2)= 1 $ إذا كان $ s_1 $ و $ s_2 $ موجودة في نفس الفئة و $ 0 $ خلاف ذلك. الحوسبة $ m $ مكلفة (قل، $ O (n ^ 2) $ ).

أنا أبحث عن بنية بيانات فعالة $ d $ يدعم استعلامات النموذج "المعطى $ S $ < / span>، هل $ D $ يحتوي على عنصر $ s '$ في نفس فئة المعادلات مثل < Span Class="حاوية الرياضيات"> $ S $ "؟
نهج ساذج هو البحث عنصري عناصر حسب العنصر في $ D $ واختبار، ولكن هل هناك حل آخر؟

Answer 1

أفضل ما يمكنك القيام به هو تتبع جميع المعادلات المعروفة حاليا باستخدام هيكل بيانات النقابة.في البداية، كل عنصر في المجموعة الخاصة.كلما وجدت أن عنصرين يعادلان، تقوم بدمج مجموعاتهم (عبر عملية نقابية).

بعد ذلك، أفضل ما يمكنك القيام به للرد على قائمة الاستعلام هو التعداد فوق جميع المجموعات (بخلاف واحد لا يحتوي على $ s $ )، ابحث عنممثل $ x $ لكل مجموعة من هذا القبيل، واختبار ما إذا كان $ S $ يعادل $ x $ .