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*/
Regards!!
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | Radewoosh | 3415 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | XVIII | 3345 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
Auto comment: topic has been updated by Vesper_Lynd (previous revision, new revision, compare).
Hello, actually I got a same question on Kattis, and the problem link is Problme Link
You can use Welsh-Powell Algorithm for this, it produces a better result. Here is the link to a paper Link
but i need to know a test case where my solution fails can u help me>>
Can you explain your code a bit? I am a bit confused!!
basically what i am doing is using bfs to move onto each node and then checking for that node all the nodes directly connected to it and storing their colour in set after that i am iterating from 1 to 1000 coz no of vertices given was 1000 to see which number is not in that set and if the number is not in the set we will assign the vertex that colour 'i' and in this way we will do it for all the vertices!!
Okay, but how can you assure that, you already know the colors the connected components of a node. You have to start the coloring process from a single node, Let us say we have a graph with 5 nodes [0,1,2,3,4,] With edges:- 0-2, 0-3, 0-4, 1-2, 1-3, 1-4, these are undirected edges, when you dry run your algorithm on this, you pick up the vertex 0, and then find the colors of its connected nodes 2,3,4 but they are uncolored as well, so how can you proceed!
in that case set will be empty and it will select i=1 for that vertex and keep on working fine!!