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

المپدیا

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

ابزار کاربر

ابزار سایت


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

مجموعه‌ی نامهربان

یک روز به شنگول و منگول، گراف جهت‌دار نیمه‌زیبای ‎G‎ را دادند و بهشان گفتند که در این گراف، اندازه بزرگ‌ترین «مجموعه‌ی ‎نامهربان»‎ را پیدا کنید. اگر نمی‌دانید «‎گراف جهت‌دارِ نیمه‌زیبا‎«‎ یا «‎مجموعه‌ی نامهربان‎«‎ چیست (بالطّبع نمی‌دونین‎!) ، متن زیر را بخوانید.

به یک گراف جهت‌دار ‎G‎ نیمه‌زیبا گویند، اگر که زیر مجموعه‌ای دلخواه از راس‌هایش انتخاب شده باشند. این زیر مجموعه را «‎مجموعه راس‌های زیبا‎«‎ می‌نامیم‎!‎

به مجموعه‌ی ‎S‎ از راس‌ها در گراف جهت‌دار ‎G «نامهربان»‎ گویند اگر ‎S‎ زیر مجموعه‌ی «‎مجوعه راس‌های زیبا‎«‎ بوده و هر راس دلخواه ‎v‎ از آن، سه خاصیت زیر را داشته باشد :

  • v‎ به حداقل یک راس از ‎S‎ یال داشته باشد.
  • حداقل یک راس از ‎S‎ به ‎v‎ یال داشته باشد.
  • v‎ به راس‌هایی که عضو ‎S‎ نیستند، یال نداشته باشد.

حالا به شنگول و منگول کمک کنید تا ‎«اندازه»‎ بزرگ‌ترین مجموعه‌ی نامهربان در گراف ‎G‎ را پیدا کنند.

ورودی

  • در سطر اول ورودی، به ترتیب دو عدد ‎n‎ و ‎m‎ داده‌ شده است که ‎n‎ برابر تعداد راس‌های گراف و m‎ برابر تعداد یال‌های گراف می‌باشد.
  • در هر سطر از ‎m‎ سطر بعدی، به ترتیب دو عدد متفاوت vi‎ و ‎vj‎ آمده، به این معنا که راس ‎vi‎ به راس ‎vj‎ یال دارد.
  • در سطر آخر ورودی، ‎n‎ عدد آمده است، عدد ‎i‎ام این دنباله برابر ‎1‎ است اگر که راس ‎i‎ام،رعضو مجموعه راس‌های زیبا باشد و برابر ‎0‎ است اگر که راس ‎i‎ام، عضو مجموعه راس‌های زیبا نباشد.
  • 0n100000
  • 0m1000000

خروجی

در خروجی تنها یک عدد چاپ کنید که نشان دهنده اندازه‌ی بزرگ‌ترین زیر مجموعه‌ی نامهربان باشد.

محدودیت‌ها

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

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

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

ابزار صفحه