المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی انتخاب تیم:دوره ی ۱۷:سوال ۶

Killall

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

برنامه‌ای بنویسید که:

  • پردازه‌ها و ارتباط‌هایشان را از ورودی بخواند.
  • کم‌ترین تعداد پیغام خطا را برای کشتن همه‌ی پردازه‌ها به‌دست آورد.
  • ترتیب کشتن پردازه‌ها با کم‌ترین تعداد پیغام خطا را در خروجی بنویسد.

ورودی

  • در سطر اول ورودی، $n$ تعداد پردازه‌ها و $m$ تعداد ارتباط‌های میان‌پزدازه‌ای با فاصله از هم نوشته شده است. پردازه‌ها از ۱ تا $n$ شماره‌گذاری شده‌اند.
  • در هر یک از $m$ سطر بعد، دو عدد صحیح $i$ و $j$ ($1\leq i,j \leq n$) با فاصله از هم آمده‌اند که نشان می‌دهد پردازه‌های $i$ و $j$ مستقیما با هم ارتباط دارند. دو پردازه بیش از یک ارتباط مستقیم برقرار نمی‌کنند. یک پردازه با خودش نیز ارتباط برقرار نمی‌کند.

اندازه‌ی ورودی‌هایی که برای نمره‌دهی به برنامه‌ی شما داده می‌شود در جدول زیر آمده است. البته بعضی از این تست‌ها باهم در یک گروه قرار دارند و در مجموع ۲۰ گروه تست وجود دارد.

شما می‌توانید نتیجه‌ی تست‌هایی که با علامت ستاره مشخص شده‌اند را در طول امتحان مشاهده کنید.

خروجی

در سطر اول خروجی، کم‌ترین تعداد پیغام خطایی را بنویسید که برای کشتن همه‌ی پردازه‌ها فرستاده می‌شود. در سطر دوم، شماره‌ی $n$ پردازه را با فاصله از هم به ترتیبی بنویسید که کشتن پردازه‌ها به آن ترتیب، تعداد پیغام‌های خطا را کمینه می‌کند.

محدودیت‌ها

  • محدودیت زمان: ۳ ثانیه
  • محدودیت حافظه: ۱۰۰ مگابایت

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

ورودی نمونه خروجی نمونه
5 5
1 2
2 3
3 4
4 1
2 5
6
2 4 1 3 5

ابزار صفحه