# Poj Solution 1419

```http://poj.org/problem?id=1419

/* @author:zeropinzuo */
import java.io.*;
import java.util.*;

public class Main{
static Scanner cin;
public static void main(String args[]){
cin = new Scanner(System.in);

int m = cin.nextInt();
for(int i=0;i< m;i++)
run();
}

static void run(){
int n = cin.nextInt();
int k = cin.nextInt();

Graph graph = new Graph(n);
for(int i=0;i< k;i++)

graph.Coloring(0);
System.out.println(graph.maxBlack);
graph.record.print();
}
}

class Graph{
int n;
Node[] nodes;

int maxBlack=-1;
Record record;

public Graph(int n){
this.n = n;

nodes = new Node[n];
for(int i=0;i< n;i++)
nodes[i] = new Node();

record = new Record();
}

}

void Coloring(int colored){
if(colored< n){
int position=0;
while(nodes[position].color != 0)
position = (position+1)%n;
Node node = nodes[position];

node.color = 'b';
if(node.check() == true)
Coloring(colored+1);

node.color = 'w';
Coloring(colored+1);

node.color = 0;
return;
}

int tmp = countBlack();
if(tmp > maxBlack){
maxBlack = tmp;
record.clear();

for(int i=0;i< n;i++)
if(nodes[i].color == 'b')
}

}

int countBlack(){
int count=0;
for(int i=0;i< n;i++)
if(nodes[i].color == 'b')
count++;
return count;
}
}

class Node{
char color=0;

void setColor(char c){
color = c;
}

}

boolean isEdgeColored(){
if(n.color == 0)
return false;
return true;
}

boolean check(){
if(color=='w')
return true;

if(n.color=='b')
return false;
return true;
}
}

class Record extends ArrayList< Integer>{
void print(){
for(Integer p:this)
System.out.print(p+" ");
System.out.println();
}

}
```
This entry was posted in poj. Bookmark the permalink.