Module: गहराई से खोजें। डीएफएस


Problem

5 /12


द्विपक्षीय ग्राफ

Theory Click to read/hide

द्विपक्षीय ग्राफ
 
द्विपक्षीय ग्राफ़ - एक ग्राफ़ जिसके शीर्षों को दो सेटों में विभाजित किया जा सकता है ताकि प्रत्येक किनारा जोड़े को जोड़े विभिन्न सेटों से शिखर।


अक्सर द्विपक्षीय ग्राफ़ के संदर्भ में, रंगों कोने की अवधारणा का उपयोग किया जाता है। किसी ग्राफ़ को दो भागों में विभाजित करना रंग इसके शीर्षों को दो अलग-अलग रंगों से रंगना कहा जाता है। प्रत्येक किनारे को एक अलग रंग के शीर्षों को जोड़ना चाहिए।

<कोड>डीएफएस। 
 

एल्गोरिदम

हम एक मनमाने शीर्ष से पेंटिंग शुरू करते हैं, जिसे हम मनमाने रंग से पेंट करते हैं।
प्रत्येक किनारे से गुजरते समय, अगले शीर्ष को विपरीत रंग में पेंट करें।
यदि, पड़ोसी शीर्षों पर पुनरावृति करते समय, हमें एक ऐसा शीर्ष मिलता है जो पहले से ही उसी रंग में रंगा हुआ है जिस रंग में वर्तमान है, तो ग्राफ़ में एक विषम चक्र है, जिसका अर्थ है कि यह द्विदलीय नहीं है।

Problem

एक ग्राफ़ को द्विदलीय कहा जाता है यदि इसके शीर्षों को दो रंगों में रंगा जा सकता है ताकि एक ही रंग के शीर्षों को जोड़ने वाले किनारे न हों (अर्थात, प्रत्येक किनारा पहले रंग के शीर्ष से दूसरे रंग के शीर्ष तक जाता है) ।
एक ग्राफ दिया। यह जाँचना आवश्यक है कि क्या यह द्विदलीय है, और यदि ऐसा है, तो इसके शीर्षों को रंगें।
 
इनपुट
पहली पंक्ति में पहले संख्या N होती है - ग्राफ़ के शीर्षों की संख्या (100 से अधिक नहीं होती)। अगला आसन्नता मैट्रिक्स आता है - एक NxN 0 और 1 का मैट्रिक्स (0 का मतलब कोई किनारा नहीं है, 1 का मतलब उपस्थिति है)। ग्राफ़ अप्रत्यक्ष है, बिना लूप के।
 
छाप 
पहली पंक्ति में कोई एक संदेश 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