I was given the assignment problem related to finding chromatic number of the graph and i was able to write a solution at that time,but i realised from my friend that it is an NP hard problem and i used "BFS" to just implement so i think it should fail at some test case, so can anybody help me finding the test case to prove it wrong!!
/*Here is the code*/
set tot; map<lli,lli> colour1; void bfs1() { queue q; q.push({1,1}); while(!q.empty()) { lli x=q.front().first; lli y=q.front().second; q.pop(); if(vis[x]) continue; vis[x]=1; set s; for(int j=0;j<v[x].size();j++) { if(vis[v[x][j]]==0) { q.push({v[x][j],x}); } s.insert(colour1[v[x][j]]); } for(int i=1;i<=1000;i++) { if(s.count(i)==0) { colour1[x]=i; tot.insert(i); break; } } s.clear(); } }
Regards!!