• • You are given an undirected graph and two colors, black and white.  write  a program to find the maximum number of nodes that can be colored with black such way that no two connected nodes colored with black. For example below undirected graph ,the maximum number of nodes that can be colored with black would be 3. ```#include <iostream>
#include<list>
using namespace std;

// data structure for undirected graph ,adjacency list
class G
{
int no_of_nodes;
public:
G(int no_of_nodes)
{
this->no_of_nodes = no_of_nodes;
}

void connect_edge(int u, int v)
{
// connect u to v
// graph is undirected to connect v to u
// connect v to u
}
// getter function
int getNum_of_nodes(){ return no_of_nodes;}
};

int max_black_nodes = -9999999;

void solve(int v,G *g, bool *isColored, char *color_of_node)
{

// base condition
if(v > 6)
{
int  black_count = 0;
int node_count = g->getNum_of_nodes();
for(int i=1; i < node_count; i++)
{
if( color_of_node[i] == 'b')
black_count++;
}
if( black_count > max_black_nodes)
max_black_nodes = black_count;

return;
}

// check whether node v ,can be colored with black
bool can_v_color_with_black = true;
list<int>::iterator it;

{
if(isColored[*it] && color_of_node[*it] == 'b')
{
can_v_color_with_black = false;
break;
}

}

isColored[v] = true; // set v as colored

if(can_v_color_with_black)
{
// color node v with black
color_of_node[v] = 'b';
solve(v + 1,g, isColored,color_of_node);
}

// color node v with white
color_of_node[v] = 'w';
solve(v + 1,g, isColored,color_of_node);

// back track, reset isColored
isColored[v] = false;

}

int main() {

// init graph
G graph(7);
graph.connect_edge(1,3);
graph.connect_edge(1,2);
graph.connect_edge(2,4);
graph.connect_edge(2,5);
graph.connect_edge(3,6);
graph.connect_edge(3,4);
graph.connect_edge(4,6);
graph.connect_edge(6,5);

//helper data for solving problem
bool isColored;
char color_of_node;

for(int i=0; i < 7; i++)
{
isColored[i] = false;
// make all node with black color
color_of_node[i] = 'b';
}

solve(1,&graph,isColored,color_of_node);

cout << "max black node would be " << max_black_nodes << endl;

return 0;
}
```