chromatic number of the graph!!
Разница между en1 и en2, 723 символ(ов) изменены
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!!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Vesper_Lynd 2019-05-01 16:57:54 723
en1 Английский Vesper_Lynd 2019-05-01 16:56:42 1136 Initial revision (published)