$n$ کشور متقاضی برگزاری مسابقات جام جهانی فوتبال هستند. میزبان مسابقات به صورت زیر انتخاب میشود:
به ازای هر تیم $i$ و $j$ میدانیم در صورتی که کمیته بخواهد از میان این دو تیم یکی را انتخاب کند، کدام تیم حذف میشود.
شما باید برنامهای بنویسید که با گرفتن اطلاعات ورودی، تمام تیمهایی که شانس میزبانی مسابقات را دارند را به دست آورد.
در سطر اول خروجی تعداد کاندیدای دارای شانس میزبانی و در سطر بعدی آنها را به ترتیب صعودی چاپ نمایید.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 2 01 00 | 1 1 |
| 3 001 100 010 | 3 1 2 3 |
پاسخ
فرض کنید گراف $G$ یک گراف $n$ راسی کامل جهتدار باشد که جهت یال بین دو راس $u$ و $v$ به سمت راسی باشد که کمیته مسابقات در صورت انتخاب بین دو کشور $u$ و $v$ آن کشور را انتخاب میکند (و کشور دیگر را حذف میکند).
اگر کشور $r$ برای میزبانی مسابقات انتخاب شده باشد، میدانیم به ازای هر راس $u \neq r$ یک کشور $f(u)$ وجود دارد که باعث حذف کشور $u$ شده است. همچنین واضح است کهیال بین دو راس $u$ و $f(u)$ به سمت $f(u)$ است. فرض کنید از گراف $G$ یالهای بین $u$ و $f(u)$ ها را انتخاب کنیم و بقیهیالها را حذف کنیم و گراف جدید را $G'$ بنامیم. میتوان نشان داد که گراف $G'$ یک درخت ریشه دار به ریشه $r$ است که تمام یالهای آن به سمت ریشه است. پس از تمام رئوس گراف یک مسیر به سمت راس $r$ وجود دارد.
همچنین در صورتی که تمام رئوس گراف مسیری به سمت راس $r'$ داشته باشند، اجتماع این مسیرها گرافی شبیه به $G'$ به ریشه $r'$ تولید میکند که میتوانیم با استفاده از آن طوری مراحل انتخاب کشور میزبان را بسازیم که کشور $r'$میزبان مسابقات شود.
پس کشور $u$ قابلیت میزبانی مسابقات را دارد اگر و فقط اگر در گراف $G$ تمام رئوس مسیری به سمت راس $u$ داشته باشند.
حال برای بهدست آوردن تمام رئوسی که شرط بالا را دارند، کافیست گراف را به مولفههای قویاً همبند افراض کنیم و رئوس مولفهای که به هیچ مولفه دیگر یالی ندارد را به عنوان جواب انتخاب کنیم.
پیچیدگی
افراض گراف به مولفههای قویاً همبند را میتوان در زمان $o(n+e)$ انجام داد. همچنین انتخاب مولفهای که به مولفههای دیگر یالی ندارد را میتوان در زمان $o(e)$ انجام داد. پس سوال را میتوان در زمان $o(n+e) = o(n^2)$ حل کرد.