Graph Coloring Problem -- GCP

import java.util.*;

import java.io.*;

class demo

{

int m,n;

int x[],graph[][];

void mcolor(int k)

{

int i;

while(1)

{

callnextvalue(k);

if(x[k]==o)break;

if(k==n)

{

for (i=1;i<=n;i++)

System.out.println(" "+x[i]);

System.out.println();

}

else

mcolor(k+1);

}

}

int callnextvalue(int k)

{

int j;

while(1)

{

x[k]=(x[k]+1)%(m+1);

if(x[k]==0) return 0;

for(j=1;j<=n;j++)

if(graph[k][j]&&x[k]==x[j])

break;

if(j==n+1) return 0;

}

}

public static void main(String arg[])

{

int i,e,a,b;

Scanner in=new Scanner(System.in);

System.out.println("Enter the verticesS");

System.out.println(n);

System.out.println("Enter no. of edges:");

e=in.nextInt();

for(i=1;i<e;i++)

{

System.out.println("Enter edge:");

a=in.nextInt();

b=in.nextInt();

graph[a][b]=1;

graph[b][a]=1;

}

for(i=1;i<=n;i++)

x[i]=0;

System.out.println("Enter no. of colors: )";

cin>>m;

System.out.println("Following are no. of ways in which nodes can be colored");

mcolor(1);

}

}

----------------------------------------------------------------------

         OUTPUT

Enter the vertices

5

Enter no of edges:

7

Enter edge:

1 2

Enter edge:

2 3

Enter edge:

3 4

Enter edge:

4 5

Enter edge:

5 1

Enter edge:

1 3

Enter edge:

2 5

Enter no. of colors:

3

Following are no. of ways in which nodes can be colored

1 2 3 1 3

1 2 3 2 3

1 3 2 1 2

1 3 2 3 2

2 1 3 1 3

2 1 3 2 3

2 3 1 2 1

2 3 1 3 1

3 1 2 1 2

3 1 2 3 2

3 2 1 2 1

3 2 1 3 1