Processing math: 34%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:آزمون های اینترنتی ۸۹ تا ۹۱:سوال ۶۵

Graph Oddity

شما در صورتی از این سوال نمره کسب می‌کنید که به همه تست ها پاسخ درست بدهید.

به شما گراف بی‌جهت ساده همبند ‎G‎ با تعداد فردی رأس داده شده است. فرض کنید ‎k‎ برابر باشد با کم‌ترین عدد فردی که درجه تمام رئوس ‎G‎ کم‌تر یا مساوی آن است.

شما باید رئوس گراف را با اعداد ‎1‎ تا ‎k‎ طوری رنگ کنید که رنگ هر دو رأس مجاور متفاوت باشد‎.‎

ورودی

در سطر اول ورودی عدد فرد ‎1n9999‎ نماینده تعداد رئوس گراف و ‎1m105‎ نماینده تعداد یال‌های گراف آمده است‎. ‎ در ‎m‎ سطر بعدی یال‌های گراف آمده‌اند‎. ‎ ورودی طوری است که سؤال حتماً دارای جواب باشد‎. ‎

خروجی

در سطر اول خروجی عدد ‎k‎ را چاپ کنید و در ‎n‎ سطر بعدی رنگ رئوس گراف را به ترتیب چاپ نمایید‎. ‎

محدودیت‌ها

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

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

ورودي نمونه خروجي نمونه
3 2‎
1 3‎
3 2
‎‎3‎
1
‎1
2
7 8‎
‎1 4
4 2
‎2 6
6 3
3 7
4 5
‎5 6
5 2
3‎
1
1
1
2
3‎
2
2

پاسخ

فرض کنید رئوس گراف را به ترتیبی دلخواه روی یک خط چیده‌ایم و آنها را از چپ به راست مطابق با روش زیر رنگ می‌کنیم:

برای رأس ‎v‎ مجموعه‌ی ‎A‎ را مجموعه‌ی رنگهای رئوسی که همسایه‌ی ‎v‎ هستند و تا به حال رنگ شده‌اند در نظر بگیرید. رنگ رأس ‎v‎ برابر است با کم‌ترین عدد طبیعی که در مجموعه‌ی ‎A‎ وجود ندارد‎.

‎ با این روش رنگ‌آمیزی تعداد رنگ‌های مورد نیاز حداکثر ‎\bigtriangleup‎ + ‎1‎ است. زیرا به ازای هر رأس، مجموعه‌ی ‎A‎ حداکثر ‎\bigtriangleup‎ تا عضو دارد و بنابراین رنگ هر رأس حداکثر برابر ‎\bigtriangleup‎ + ‎1‎ می‌شود‎.

‎ این الگوریتم درصورتی که ‎\bigtriangleup‎ زوج باشد، مورد قبول است، زیرا در این صورت ‎k‎ برابر ‎\bigtriangleup‎ +‎1‎ می‌شود و ما می‌توانیم گراف را با ‎k‎ رنگ، رنگ آمیزی کنیم. اما در صورتی که ‎\bigtriangleup‎ فرد باشد، ‎k‎ برابر خود ‎\bigtriangleup‎ می‌شود و این روش مورد قبول نیست. اما اگر در این روش کاری کنیم که به ازای هر رأس اندازه‌ی مجموعه‌ی ‎A‎ حداکثر ‎k-1‎ شود، آنگاه می‌توانیم مطمئن باشیم که حداکثر از ‎k‎ رنگ استفاده کرده‌ایم. برای این کار کافی است ترتیبی از رأس‌ها ارائه دهیم که در آن به ازای هر رأس حدکثر ‎k-1‎ تا از همسایه‌هایش در سمت چپش قرار داشته باشد.

درحالتی که ‎\bigtriangleup‎ فرد است، چون تعداد رئوس هم فرد است، حداقل یک رأس وجود دارد که درجه‌ی آن از ‎\bigtriangleup‎ کم‌تر باشد.اسم این رأس را ‎u‎ می گذاریم.

درخت ریشه داری را درنظر بگیرید که ریشه‌ی آن رأس ‎u‎ باشد. اگر ترتیب رئوس در الگوریتم بالا، به ترتیب عمق رئوس در این درخت باشد (از پایین به بالای درخت)، به جز ریشه درخت که رأس ‎u‎ است، بقیه‌ی رئوس حداقل یک همسایه (پدر آن رأس در درخت ریشه دار) در سمت راست خود دارند. رأس ‎u‎ هم حداکثر ‎\bigtriangleup‎ -‎1‎ همسایه دارد. بنابراین هر رأس در سمت چپ خود حداکثر ‎\bigtriangleup‎ -‎1‎ یال دارد. پس اگر الگوریتم بالا را با این ترتیب از رأس‌ها اجرا کنیم، حداکثر ‎\bigtriangleup‎ رنگ استفاده خواهد شد‎.‎

پيچيدگي

الگوریتم رنگ‌آمیزی که در ابتدا مطرح شد درصورتی که برای نگهداری گراف از لیست مجاورت استفاده شود از ‎O(e)‎ است، زیرا در آن، هر رأس و لیست همسایه‌هایش دقیقا یک بار بررسی می‌شود. در صورتی که ‎\bigtriangleup‎ فرد باشد، باید قسمت دوم الگوریتم که ارائه‌ی ترتیبی از رئوس برحسب درخت ریشه‌دار است نیز اجرا شود. این قسمت نیز می‌تواند با استفاده از یکی از الگوریتم‌های ‎BFS‎ یا DFS پیاده سازی شود که هر دو از ‎O(e)‎ هستند. بنابراین کل الگوریتم از ‎O(e)‎ خواهد بود.


ابزار صفحه