/*

测试数据

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

*/

import java.util.*;

/**
* 描述m着色问题，问题见《算法设计与分析》（王晓东），第五章回溯法
* @author 2008-8-2
*/

public class Coloring
{
private int n=0;//结点数
private int colored [];//着色情况
private int m=0;//颜色数,下标0
private boolean Graph[][];//下标从0开始
private boolean solve = false;

public Coloring()
{

}

public void mColor(int m,int n,boolean [][] g )
{
this.m = m;
this.n = n;
Graph = g;
solve = false;
colored = new int[n];

backtrace(0);
if(!solve)
{
System.out.println("Thres is no solution.");
}
}

//下标从0开始
private void backtrace(int i)
{
if(i==n)
{
System.out.println("Solution ：");
for(int j=0;j<n;j++)
{
System.out.print((j+1)+"->"+colored[j]+" ");
}
System.out.print("\n");
solve = true;
}
else
{
for(int j=0;j<m;j++)//m种颜色
{
colored[i] = j;

if(ok(i))//在第i个点上涂j颜色是否合适
{
backtrace(i+1);
}
}
}
}

private boolean ok(int i)
{
for(int j=0;j<n;j++)
{
if(Graph[i][j] && i!=j && colored[j]==colored[i])
{
return false;
}
}
return true;
}

public static void main(String args[])
{
Scanner scan = new Scanner(System.in);
Coloring c = new Coloring();

System.out.println("How many country on the map:");
int n = scan.nextInt();

System.out.println("How many color:");
int m = scan.nextInt();

boolean g[][] = new boolean[n][n];

for(int i=0;i<n;i++)
{
Arrays.fill(g[i], false);
}

System.out.println("Enter num(1 to n) of the two country which are connected(0 0 for end):");
while(scan.hasNext())
{
int a = scan.nextInt();
int b = scan.nextInt();
if(a==0 && b==0)
{
break;
}
else
{
if(a<0 || b<0 || a>n || b>n)
{
System.out.println("Make true the two number are between 1 and n");
}
else
{
g[a-1][b-1] = true;
g[b-1][a-1] = true;
}
}
}
c.mColor(m, n, g);
}
}