المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی تابستان:دوره‌ی ۲۰:عملی:سوال ۵

درخت همیشه خوب

مهدی به تازگی با نظریه گراف آشنا شده و درخت‌ها را مورد بررسی قرار داده است. او به درخت‌هایی علاقه‌مند است که تعداد برگ‌هایشان از تعداد رئوس غیر برگشان بیش‌تر است. به همین دلیل او این درخت‌ها را درخت‌های خوب می‌نامد. با توجه به علاقه شدید او به این خاصیت در درخت‌ها او به دنبال درخت‌هایی می‌گردد که همیشه خوب باشند. او برای این‌که ببیند یک درخت همیشه خوب است، ابتدا بررسی می‌کند که خود درخت خوب باشد و سپس می‌خواهد ببیند آیا می‌توان راسی را از درخت حذف کرد که جنگل باقی‌مانده باز هم خخوب باقی بماند. او می‌خواهد آن‌قدر این کار را بکند تا هیچ راسی در درخت باقی نماند، اگر درختی چنین ویژگی‌ها را داشت، احتمالا مهدی خیلی خوشحال می‌شود، زیرا یک درخت همیشه خوب یافته است. لازم به ذکر است هنگام حذف کردن یک راس از یک درخت آن راس و همه‌ یال‌های مجاورش به همراه رئوسی که درجه‌شان صفر شده از درخت حذف می‌شوند.

در این مسئله قرار است شما به مهدی کمک کنید و بگویید آیا یک جنگل همیشه خوب است یا نه و در صورت همیشه خوب بودن ترتیبی از حذف رئوس را ارائه دهید که در همه مراحل جنگل باقی‌مانده همیشه خوب باقی بماند.

ورودی

  • در سطر اول ورودی $n$ تعداد رئوس جنگل ($1\leq n \leq 10^6$) می‌آید.
  • در $n$ سطر بعدی در خط $i$ام ابتدا $k$ تعداد رئوس مجاور راس $i$ام می‌آید و سپس $k$ عدد می‌آید که شماره رئوس مجاور راس $i$ام می‌باشند. رئوس از ۱ تا $n$ شماره‌گذاری شده‌اند.

خروجی

  • در سطر اول خروجی اگر دخت ورودی درختی همیشه خوب است، عبارت “Always Good Tree” را چاپ نمایید. اگر درخت ورودی، درختی همیشه خوب نیست درتنها خط خروجی عبارت “Discouraging Tree” را چاپ نمایید.
  • در سطر دوم ابتدا تعداد رئوسی که مستقیما حذف می‌کنید را بنویسید و سپس شماره رئوسی که از درخت حذف کرده‌اید را به ترتیب حذف شدن بنویسید.

محدودیت‌ها

  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

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

ورودی نمونه خروجی نمونه
5
1 2
2 1 3
2 2 4
2 3 5
1 4
Discouraging Tree
5
4 2 3 4 5
1 1
1 1
1 1
1 1
Always Good Tree

ابزار صفحه