Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۰:عملی:سوال ۱۹

زیردرخت DFS

گراف ساده و بدون جهت G و همچنین زیردرخت فراگیر T از آن داده شده است. می‌خواهیم تمام رئوسی مثل v را بیابیم که دارای این خاصیت باشند: بتوان از راس v، DFS ای زد که درخت DFS حاصل از آن برابر T شود. توجه کنید که در DFS می‌توانیم رئوس مجاور هر راس را به هر ترتیب دلخواهی پیمایش کنیم.

ورودي

در فایل ورودی ابتدا n، تعداد رئوس گراف و m، تعداد یال‌های آن آمده است. سپس در n1 سطر بعد در هر سطر دو عدد به نشانه دو انتهای یک یال از T‌ آمده است. بقیه یال‌های گراف که در T نیامده‌اند در mn+1 سطر بعد به همین صورت می‌آیند.

خروجي

در سطر اول فایل خروجی، k، تعداد رئوس دارای خاصیت فوق را بنویسید. سپس در k سطر بعد، شماره‌ی این رئوس را به ترتیب صعودی بنویسید. فرض کنید که n30000 و mn100.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
4 4
1 2
2 3
2 4
3 4
‎2
3
4‎

ابزار صفحه