المپدیا

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

ابزار کاربر

ابزار سایت


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

گراف جهت‌دار بدون دور ستاینده

در گراف جهت‌دار بدون دور $D$، برای هر راس $v$ تابع $a(v)$ به این صورت تعریف می‌شود:

$$a(v)=\{u|v \xrightarrow{*} u \}$$

که $v \xrightarrow{*} u$ یعنی این‌که مسیری (با توجه به جهت یال‌ها) از $v$ به $u$ وجود دارد. به شما لیست تمام $a(v)$ ها به ترتیب نامشخص داده شده است، شما باید گراف جهت‌دار بدون دوری بیابید که در شرایط ذکر شده صدق بکند و از میان تمام این گراف‌ها، گرافی را بیابید که کم‌ترین یال را داشته باشد.

ورودی

در فایل ورودی نخست $n$ تعداد راس‌های گراف داده شده است. سپس در $n$ سطر بعدی در سطر $i$ ام نخست اندازه‌ی مجموعه‌ی $a(v_i)$ سپس نام راس‌های اعضای آن مجموعه به ترتیبی نامشخص آمده است. نام هر راس عدد صحیح می‌باشد. (نام راس‌ها لزوما ربطی به شماره‌ی سطری که در آن قرار دارند ندارد).

خروجی

در فایل خروجی در $n$‌ سطر، در سطر $i$ ام نام راس $v_i$ سپس تعداد فرزندان مستقیم آن راس را بنویسید.($1\leq n \leq 200$)

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

ورودي نمونه خروجي نمونه
5
4 10 11 7 8
2 9 11
1 10
1 11
3 8 10 11
7 1 8
9 1 11
10 0
11 0
8 2 10 11

ابزار صفحه