====== Graph Oddity ====== ==== شما در صورتی از این سوال نمره کسب می‌کنید که به همه تست ها پاسخ درست بدهید. ==== به شما گراف بی‌جهت ساده همبند ‎$G$‎ با تعداد فردی رأس داده شده است. فرض کنید ‎$k$‎ برابر باشد با کم‌ترین عدد فردی که درجه تمام رئوس ‎$G$‎ کم‌تر یا مساوی آن است. شما باید رئوس گراف را با اعداد ‎$1$‎ تا ‎$k$‎ طوری رنگ کنید که رنگ هر دو رأس مجاور متفاوت باشد‎.‎ ===== ورودی ===== در سطر اول ورودی عدد فرد ‎$1 \leq n \leq 9999$‎ نماینده تعداد رئوس گراف و ‎$1 \leq m \leq 10^5$‎ نماینده تعداد یال‌های گراف آمده است‎. ‎ در ‎$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)$‎ خواهد بود. * [[سوال ۶۶|سوال بعد]] * [[سوال ۶۴|سوال قبل]]