Question

You are given a set of ‘n’ chemical compounds which have to be packed in two boxes. Some of ​​the​​ chemicals​ ​may​ ​react​​ with​ ​other ​​chemical s​​and​​ should​​ not ​​be ​​packed​​ in​​ the​​ same​​ box.
Code an ​efficient algorithm in/C++ that determines if it is possible to safely pack these chemicals in two boxes and if so, then print which chemicals should go in Box-1​​ and​​ which​​ in​​ Box-2.
n6
C0: C1,C2
C1: C0,C3,C5
C2: C0
C3: C4,C1
C4: C3
C5: C1

Answer 1

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int> > g;
vector<bool> colors;
vector<bool> used;

bool ok = true;

void dfs(int v, bool color)
{
used[v] = true;
colors[v] = color;
for (int i = 0; i < g[v].size(); ++i)
{
int to = g[v][i];
if (!used[to])
{
dfs(to, !color);
}
else
{
if (colors[to] == colors[v])
{
ok = false;
return;
}
}
}
}
int main()
{
//the main idea of the algorithm is to build graph and check if is Bipartite using dfs
int n;
cin >> n;
g.resize(n);
colors.resize(n, false);
used.resize(n, false);
for (int i = 0; i < n; ++i)
{
cout << "Enter number of chemicals it may react with: \n";
int m;
cin >> m;
while(m--)
{
int x;
cin >> x;
g[i].emplace_back(x);
}
}

dfs(0, true);
if (ok == false)
{
cout << "No solution\n";
}
else
{
cout << "First box\n";
for (int i = 0; i < n; ++i)
{
if (colors[i] == true)
{
cout << "C" << i << " ";
}
}

cout << endl;

cout << "Second box\n";
for (int i = 0; i < n; ++i)
{
if (colors[i] == false)
{
cout << "C" << i << " ";
}
}

cout << endl;
}
}