#include<iostream>#include<vector>#include<unordered_set>usingnamespacestd;
boolbipartite(vector<int> *edges, int n){if (n == 0) {returntrue; }unordered_set<int> sets[2];vector<int> pending; sets[0].insert(0); pending.push_back(0);while (pending.size() > 0) {int current = pending.back(); pending.pop_back(); //here pending vector is being used as a stackint set_of_current_element = sets[0].count(current) > 0 ? 0 : 1;//is the current element is in pending then it has to be in one of the sets, either 0 or 1.//now iterating over all of its neighboursfor (int i = 0; i < edges[current].size(); i++) {int adjacent = edges[current][i];if (sets[0].count(adjacent) == 0 && sets[1].count(adjacent) == 0) { sets[1 - set_of_current_element].insert(adjacent); pending.push_back(adjacent); }else//in this case the element is in one of the sets {if (sets[set_of_current_element].count(adjacent) > 0) {returnfalse; } } } }returntrue;//in this code we have considered that or graph is fully connected. there are not disconnected components}intmain(){while (true) {int n;cin >> n;if (n == 0) {return0; }vector<int> *edges = newvector<int>[n];int m;cin >> m;for (int i = 0; i < m; i++) {int j, k;cin >> j >> k; edges[j - 1].push_back(k - 1); //considering that the vertices are numbered from 1 to n. edges[k - 1].push_back(j - 1); //for internal calculation we will consider numbering from 0 to n-1. }bool ans = bipartite(edges, n);if (ans) {cout << "Bicolorable" << endl; }else {cout << "Not Bicolorable" << endl; }delete[] edges; }}Code language:C++(cpp)