193 - Graph Coloring

[brianfry713]

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)
}

[jporcelli1120]

The legendary brianfry of UVa strikes again thanks man

[LlatzerandToni]

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

[bluemmb22]

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 ....