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

Post by brianfry713 » Fri Feb 20, 2015 9:50 pm

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

Post by jporcelli1120 » Fri Feb 20, 2015 10:57 pm

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

Post by LlatzerandToni » Mon Mar 23, 2015 2:49 pm

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

Post by bluemmb22 » Sat Jul 25, 2015 8:37 pm

Finally I found a test that Greedy Solution does not work . :D
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 ....

Post Reply

Return to “Volume 1 (100-199)”