گراف

یک گراف جهت‌دار $G$ داریم. می‌خواهیم یک زیرمجموعه‌ی $S$ از رئوس $G$ انتخاب کنیم به طوری که برای هر راس $G-S$ مثل $x$، حداقل یک راس مانند $y$ از $S$ وجود داشته باشد به طوری که از $y$ به $x$ مسیر جهت‌دار باشد. در ضمن، $S$ باید کوچک‌ترین مجموعه با این خاصیت باشد.

در خط اول $n$ تعداد رئوس $G$ نوشته شده است. در خط‌های بعد، ماتریس مجاورت $G$ آمده است. به عبارت دیگر، در خطوط ۲ تا $n+1$ در هر خط $n$ عدد آمده است که عدد $j$ ام در سطر $i$ ام اگر راس $i$ ام به راس $j$ ام یال داشته باشد 1 است و در غیر این صورت ۰ است.

در سطر اول حداقل تعداد رئوس $S$ را بنویسید. شماره‌های این رئوس را بنویسید. شماره‌ی یک راس یک عدد بین ۱ و $n$ می‌باشد. در صورت وجود بیش از یک جواب:نوشتن یک جواب لازم و کافی است.

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

• سوال بعد
• سوال قبل