Module: جستجوی عمیق DFS


Problem

5 /12


نمودار دو بخشی

Theory Click to read/hide

گراف دو بخشی
 
گراف دو قسمتی - نموداری که رئوس آن را می توان به دو مجموعه تقسیم کرد به طوری که هر یال آن را به هم متصل کند رئوس از مجموعه های مختلف.


اغلب در زمینه نمودارهای دوبخشی، از مفهوم رنگ ها رئوس استفاده می شود. تقسیم یک نمودار به دو قسمت، رنگ آمیزی رأس آن با دو رنگ متفاوت نامیده می شود. هر لبه باید رئوس رنگ متفاوتی را به هم متصل کند.

DFS. 
 

الگوریتم

نقاشی را از یک راس دلخواه شروع می کنیم که آن را با رنگ دلخواه رنگ می کنیم.
هنگام عبور از هر لبه، رأس بعدی را به رنگ مخالف رنگ کنید.
اگر در حین تکرار بر روی رئوس همسایه، راسی را پیدا کنیم که قبلاً به همان رنگ راس فعلی رنگ شده است، در این صورت یک چرخه فرد در نمودار وجود دارد که به این معنی است که دو قسمتی نیست.

Problem

یک گراف را دو قسمتی می نامند اگر رئوس آن را بتوان در دو رنگ رنگ کرد به طوری که هیچ لبه ای وجود نداشته باشد که رئوس هم رنگ را به هم متصل کند (یعنی هر یال از رأس رنگ اول به رأس رنگ دوم می رود) .
یک نمودار داده می شود. لازم است بررسی شود که آیا دوبخشی است یا خیر، و اگر چنین است، رئوس آن را رنگ آمیزی کنید.
 
ورودی
خط اول ابتدا شامل عدد N است - تعداد رئوس نمودار (از 100 تجاوز نمی کند). بعد ماتریس مجاورت می آید - یک ماتریس NxN از 0 و 1 (0 به معنای بدون لبه، 1 به معنای حضور است). نمودار بدون جهت، بدون حلقه است.
 
Imprint 
در خط اول یکی از پیام‌های YES یا NO را چاپ کنید (بسته به اینکه نمودار دو بخشی است یا خیر). اگر پاسخ بله است، در خط دوم اعداد N را چاپ کنید - رنگ هایی که رئوس را رنگ می کنند: برای ​​رنگ اول از مقدار 1 استفاده کنید. رنگ دوم - مقدار 2. راس اول باید رنگ 1 باشد.
 
نمونه‌ها
<سر> <بدن>
# ورودی خروجی
1
3
0 1 1
1 0 1
1 1 0
 نه
2
3
0 1 1
1 0 0
1 0 0
بله
1 2 2

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!