समस्या विवरण
मान लीजिए हमारे पास एक जुड़ा हुआ ग्राफ है; हमें जांचना है कि ग्राफ द्विभाजित है या नहीं। यदि दो रंगों को लागू करके ग्राफ रंगाई संभव है जैसे कि एक सेट में नोड्स को एक ही रंग से रंगा गया हो।
उदाहरण
यदि इनपुट ग्राफ (चित्र देखें) है, तो आउटपुट True होगा।

एल्गोरिदम चरण
- फ़ंक्शन insert_edge(adj, u, v) परिभाषित करें जो आसन्न सूची में किनारे जोड़ता है।
- मुख्य विधि से:
- adj[v] में प्रत्येक u के लिए:
- यदि visited[u] गलत है:
- visited[u] := सत्य
- color[u] := color[v] का उल्टा
- यदि is_bipartite_graph(adj, u, visited, color) गलत है, तो गलत वापस करें
- अन्यथा यदि color[u] == color[v], तो गलत वापस करें
- यदि visited[u] गलत है:
- सत्य वापस करें
- adj[v] में प्रत्येक u के लिए:
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
void insert_edge(vector<int> adj[], int u, int v){
adj[u].push_back(v);
adj[v].push_back(u);
}
bool is_bipartite_graph(vector<int> adj[], int v, vector<bool>& visited, vector<int>& color){
for (int u : adj[v]) {
if (visited[u] == false) {
visited[u] = true;
color[u] = !color[v];
if (!is_bipartite_graph(adj, u, visited, color))
return false;
}
else if (color[u] == color[v])
return false;
}
return true;
}
int main() {
int N = 6;
vector<int> adj_list[N + 1];
vector<bool> visited(N + 1);
vector<int> color(N + 1);
insert_edge(adj_list, 1, 2);
insert_edge(adj_list, 2, 3);
insert_edge(adj_list, 3, 4);
insert_edge(adj_list, 4, 5);
insert_edge(adj_list, 5, 6);
insert_edge(adj_list, 6, 1);
visited[1] = true;
color[1] = 0;
cout << (is_bipartite_graph(adj_list, 1, visited, color));
}
इनपुट
insert_edge(adj_list, 1, 2); insert_edge(adj_list, 2, 3); insert_edge(adj_list, 3, 4); insert_edge(adj_list, 4, 5); insert_edge(adj_list, 5, 6); insert_edge(adj_list, 6, 1);
आउटपुट
1