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 sand 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
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 << " "; } }
Numbers and figures are an essential part of our world, necessary for almost everything we do every day. As important…
APPROVED BY CLIENTS
"assignmentexpert.com" is professional group of people in Math subjects! They did assignments in very high level of mathematical modelling in the best quality. Thanks a lot
Comments
Leave a comment