C++-এ DFS ব্যবহার করে গ্রাফ বাইপার্টাইট (Bipartite) কিনা তা যাচাই করুন

মান লিজিয়ে একটি কানেক্টেড গ্রাফ দেওয়া আছে; যাচাই করুন গ্রাফটি বাইপার্টাইট কিনা। দুটি রঙ দিয়ে গ্রাফ কালার করা যায় কিনা যাতে একই সেটের নোডগুলো একই রঙ পায়।

ইনপুট:

আউটপুট: True

সমাধানের ধাপগুলো:

insert_edge() ফাংশন: adj, u, v নিয়ে এজ যোগ করুন
মেইন মেথড থেকে: প্রতিটি u ইন adj[v]-এ:

যদি visited[u] == false, visited[u]=true, color[u]=!color[v], রিকার্সিভ কল করুন
অন্যথায় যদি color[u]==color[v], false রিটার্ন করুন

true রিটার্ন করুন

উদাহরণ (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);