المپدیا

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

ابزار کاربر

ابزار سایت


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

کم‌تر رنگ‌آمیزی

گراف جهت‌دار ساده‌ی $G$ با $n$ ‌ راس داده شده است. می‌خواهیم یک رنگ‌آمیزی معتبر از $\{1,…,k\}$ برای راس‌های $G$ بیابیم که $k$ از طول (تعداد راس‌های) بزرگ‌ترین مسیر جهت‌دار در $G$ بیش‌تر نباشد.

ورودی

در اول فایل ورودی عدد $n$($1 \leq n \leq 10^4$) و در $n$‌ سطر بعدی ماتریس مجاورت $G$ آمده است.

خروجی

در فایل خروجی در صورت وجود، عدد نسبت داده شده به هر راس را با یک فاصله بنویسید. در غیر این صورت پیغام $Impossible$ را در فایل خروجی بنویسید.

محدودیت‌ها

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

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

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

پاسخ


ابزار صفحه