## 193 - Graph Coloring

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 193 - Graph Coloring

Algorithm AC in 0.029 seconds.

Create an adjacency list and mark all nodes as white.

Call a recursive function backtrack(starting on node 1)

Code: Select all

``````backtrack(int node) {
if(node == n + 1) {
if more nodes are marked as black then the best solution found so far, then keep track of which nodes are marked black.
return;
}
If(no neighbors are marked black) {
mark node black
backtrack(node + 1)
mark node white
}
backtrack(node + 1)
}
``````
Check input and AC output for thousands of problems on uDebug!

jporcelli1120
New poster
Posts: 11
Joined: Mon Jan 26, 2015 2:05 pm

### Re: 193 - Graph Coloring

The legendary brianfry of UVa strikes again thanks man

LlatzerandToni
New poster
Posts: 15
Joined: Sun Apr 23, 2006 1:35 pm

### Re: 193 - Graph Coloring

brianfry713 wrote:Algorithm AC in 0.029 seconds.

Create an adjacency list and mark all nodes as white.

Call a recursive function backtrack(starting on node 1)

Code: Select all

``````backtrack(int node) {
if(node == n + 1) {
if more nodes are marked as black then the best solution found so far, then keep track of which nodes are marked black.
return;
}
If(no neighbors are marked black) {
mark node black
backtrack(node + 1)
mark node white
}
backtrack(node + 1)
}
``````
OMG, it's true.

But this algorith becomes eternal with inputs like:

Code: Select all

``````1
100 2
1 2
2 3``````
Lol

bluemmb22
New poster
Posts: 2
Joined: Wed Jul 08, 2015 2:09 pm

### Re: 193 - Graph Coloring

Finally I found a test that Greedy Solution does not work .
this graph is ok :

5 9

2 3
2 4
2 5
3 4
3 5
4 5
1 2
1 3
1 5

Code: Select all

``````       4
/|\
1----2----3
\   \|/ |
\---5  |
\-----|
``````

answer is 2 : nodes 1,4

BUT if we have exact copy of this graph with numbers : 1',2',...,5'
and then a node with number 0 that connect 1 and 1' , algorithm get wrong answer :
/ 1 ...
0
\ 1' ...

answer is 4 but greedy solution find 3! because it's first select is 0 and then ....