====== گراف ====== یک گراف جهت‌دار $G$ داریم. می‌خواهیم یک زیرمجموعه‌ی $S$ از رئوس $G$ انتخاب کنیم به طوری که برای هر راس $G-S$ مثل $x$، حداقل یک راس مانند $y$ از $S$ وجود داشته باشد به طوری که از $y$ به $x$ مسیر جهت‌دار باشد. در ضمن، $S$ باید کوچک‌ترین مجموعه با این خاصیت باشد. ===== ورودی ===== در خط اول $n$ تعداد رئوس $G$ نوشته شده است. در خط‌های بعد، ماتریس مجاورت $G$ آمده است. به عبارت دیگر، در خطوط ۲ تا $n+1$ در هر خط $n$ عدد آمده است که عدد $j$ ام در سطر $i$ ام اگر راس $i$ ام به راس $j$ ام یال داشته باشد 1 است و در غیر این صورت ۰ است. ===== خروجی ===== در سطر اول حداقل تعداد رئوس $S$ را بنویسید. شماره‌های این رئوس را بنویسید. شماره‌ی یک راس یک عدد بین ۱ و $n$ می‌باشد. در صورت وجود بیش از یک جواب:نوشتن یک جواب لازم و کافی است. ===== محدودیت‌ها ===== * محدودیت زمان: ۲ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ===== ورودی و خروجی نمونه ===== ^ ورودی نمونه ^ خروجی نمونه ^ |6 \\ 0 1 0 0 0 0 \\ 0 0 0 0 0 0 \\ 0 1 0 1 0 0 \\ 0 0 0 0 1 0 \\ 0 0 0 0 0 1 \\ 0 0 1 0 0 0 | 2 \\ 1 3| * [[سوال ۷|سوال بعد]] * [[سوال ۵|سوال قبل]]