المپدیا

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

ابزار کاربر

ابزار سایت


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

زیردرخت DFS

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

ورودي

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

خروجي

در سطر اول فایل خروجی، $k$، تعداد رئوس دارای خاصیت فوق را بنویسید. سپس در $k$ سطر بعد، شماره‌ی این رئوس را به ترتیب صعودی بنویسید. فرض کنید که $n\leq 30000$ و $m-n \leq 100$.

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

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

ابزار صفحه