في كثير من الأحيان في سياق الرسوم البيانية ثنائية الأجزاء ، يتم استخدام مفهوم & nbsp؛ الألوان & nbsp؛ القمم. يسمى تقسيم الرسم البياني إلى قسمين & nbsp؛ تلوين & nbsp؛ رؤوسه بلونين مختلفين. يجب أن تربط كل حافة رؤوس بلون مختلف. DFS . & nbsp؛ على & nbsp؛
DFS
نبدأ الرسم من قمة عشوائية ، نرسمها بلون عشوائي. عند المرور على طول كل حافة ، قم بطلاء الرأس التالي باللون المعاكس. إذا وجدنا أثناء التكرار على الرؤوس المجاورة رأسًا مرسومًا بالفعل بنفس لون الرأس الحالي ، فهناك دورة فردية في الرسم البياني ، مما يعني أنه ليس ثنائيًا.
N
نعم & nbsp؛
NO
نعم ، & nbsp ؛ في السطر الثاني ، اطبع أرقام N - الألوان لتلوين الرؤوس: & nbsp ؛ بالنسبة للون الأول ، استخدم القيمة 1 ، من أجل اللون الثاني - القيمة 2. نبسب ؛ يجب أن يكون الرأس الأول بلون 1.
1000 ms 256 Mb Rules for program design and list of errors in automatic problem checking