مولفه‌های همبندی گراف
مساله 13 - صفحه 18 کتاب «مساله‌های الگوریتمی»: مولفه‌های همبندی
رابطه‌ی همبند بودن بین راس‌های گراف بدون جهت G به این صورت تعریف می‌شود: می‌گوییم راس u با راس v همبند است اگر و تنها اگر در گراف G مسیری از u به v وجود داشته باشد. به سادگی دیده می‌شود که این یک رابطه هم‌ارزی است. بنابراین مجموعه‌ی رئوس گراف را به زیرمجموعه‌هایی افراز می‌کند. به هریک از این مجموعه‌ها یک مولفه‌ی همبندی گراف می‌گوئیم.
مثال: گرافی با سه مولفه همبندی
برنامه‌ای بنویسید که مولفه‌های همبندی گراف داده شده‌ی G را به‌دست آورد. در سطر اول فایل ورودی، تعداد رئوس گراف، و در سطرهای بعد، نیمه پایین ماتریس مجاورت آن نوشته شده است. منظور از نیمه پایین ماتریس مجاورت، مجموعه‌ی عناصر زیر قطر اصلی آن است که به شکل یک مثلث هستند. فرض کنید که تعداد رئوس گراف از 100 بیشتر نیست.
خروجی را به این صورت در فایل خروجی بنویسید: در سطر اول، تعداد مولفه‌های همبندی و در هریک از سطرهای بعد، شماره رئوس یکی از این مولفه‌ها را بنویسید. به مثال زیر که مربوط به گراف شکل بالا است توجه کنید:
|
ورودی 8 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 |
خروجی 3 1 2 6 3 5 4 8 7 |
تگ ها
- پیشنهادی
- تازهها
- ویژهنامه
