Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userالمكونات المتصلة بقوة هي أجزاء من الرسم البياني الموجه حيث يمكن الوصول من أي رأس إلى أي رأس آخر داخل نفس المكون والعكس صحيح.
الخطوة الأولى هي تشغيل البحث العميق أولاً (DFS) لحساب أوقات الانتهاء لكل رأس في الرسم البياني.
المقلوب (Transpose) للرسم البياني الموجه هو رسم بياني يتم فيه عكس اتجاه كل حافة في الرسم البياني الأصلي.
يتم تنفيذ DFS على الرسم البياني المقلوب بترتيب تنازلي لأوقات الانتهاء لتحديد المكونات المتصلة بقوة بشكل صحيح، حيث يساعد هذا الترتيب في اكتشاف جميع الرؤوس في نفس المكون المتصل بقوة.