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<lli> tot;↵
map<lli,lli> colour1;↵
void bfs1()↵
{↵
queue<ll> 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<lli> 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();↵
}↵
}[LINK](https://pastebin.com/aKtwkNjj)↵
↵
Regards!!
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*/↵
↵
map<lli,lli> colour1;↵
void bfs1()↵
{↵
queue<ll> 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<lli> 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!!
