193 - Graph Coloring

[bourne]

If you are getting TLE then,
Backtracking with prunning should be enough to pass the time limit.

.. My AC took 0.187 seconds.

there are 2^100 possibilities....... which seems to be significantly high but prunning at different stages should reduce the time quite extensively.

Analysis :
Suppose at a certain stage the maximum number of nodes colored is 23 and there is a total of 100 nodes. Say, you are at depth 90 and you have colored 12 nodes from (1..90) , then there is no need to go any further cos you know you can color at most (12 + 10) nodes which is less than 23.
This consideration should lead you to the right path.

Can you further explain how did you prune. Pruning 2^100 cases seems to be impossible for me. I tried, but my solution still takes a lot of time for largest input.

[Jan]

Two parts will do.

1. If you assign 'black' to a vertex then assign 'white' to all the adjacent nodes.

2. As sohel suggested, suppose you have found (In a step) that you can assign 'black' to 10 nodes. Suppose in the backtrack you have assigned black to 3 nodes, and say 5 nodes are still to be checked. Then imagine that if you assign black to all the 5 nodes then total black assigned nodes will be 8. Then stop further iteration for that branch.

Hope these help.

[bourne]

I think the judge input data is very very weak. I had not submitted the problem before my last post because I analyzed the problem and found that backtracking solution will time out. Now when you guys said that backtracking is getting AC, I thought of giving it a try and got AC in 0.01sec. Now I removed the prune condition which is recommended above, and got AC with same time. This shows that the judge input data is very weak, and the key to solving this problem is to make a wild guess that your solution will not time out.

Consider the following input:

Code: Select all

1
100 2
1 2
2 3

When I ran the test case on solution without considering any pruning, I don't get the result even after waiting for a long time. But solution with pruning as specified above gives the result pretty quickly. This shows that judge has no such kind of inputs and constraint of 100 is just confusing.
Moreover I made test case with 100 nodes and 100 edges and I can't solve it even after pruning.

I just want to ask what would a person do if such a problem comes in a real contest. Would he realize that backtracking is not sufficient for this NP problem and look for GREEDY? or would he make GUESS that JUDGE's input will be weak, so let's code backtracking?

[Jan]

Np problems can't be solved by greedy. Greedy can help you to find a good bound, but backtracking is the only option (till now ).

[bourne]

Then why are the input constraints of the problem so deceptive. I wasted most of my time on this problem just because of the constraints given since no practical solution can pass if the constraints are followed strictly.

[Jan]

Make test cases and ask the admins to add them.

[dreadlord]

Hi there,

I agree with people that claims that this problem is really hard to solve in general given the problem description constraints.

Any of you has got an algorithm (deterministic, I mean, not based on random node choices that may or not lead to the actual solution) that solves this problem for a large case which is also rather symmetric in its connections?

I drop here an input case that falls into this category, a graph of 100 nodes whose connections form a ring:

Code: Select all

1
100 100
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54
54 55
55 56
56 57
57 58
58 59
59 60
60 61
61 62
62 63
63 64
64 65
65 66
66 67
67 68
68 69
69 70
70 71
71 72
72 73
73 74
74 75
75 76
76 77
77 78
78 79
79 80
80 81
81 82
82 83
83 84
84 85
85 86
86 87
87 88
88 89
89 90
90 91
91 92
92 93
93 94
94 95
95 96
96 97
97 98
98 99
99 100
100 1

So far I've found no way to solve this kind of cases with an algorithm that fully guarantees the correctness of its output and within time limits...

I got AC anyhow. I guess that input cases are actually not so extreme like this one. I also guess that people that get below 0.030 s are making not very elegant things in their programs...

Regards,

--Dread

[empo]

Wrong Answer>>>>>Cant Find Any error:::

For INPUTS------------>>>>>>>>>>>>>

Code: Select all

8
6 8
1 2
1 3
2 4
2 5
3 4
3 6
4 6
5 6

100 2
1 2
2 3

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

6 6
1 2
2 3
3 4
4 5
5 6
6 1

7 14
1 2
1 3
1 4
1 5
1 6
2 3
3 4
5 7
6 7
2 5
4 6
2 4
5 6
1 7

3 3
1 2
2 3
3 1

3 0

100 100
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54
54 55
55 56
56 57
57 58
58 59
59 60
60 61
61 62
62 63
63 64
64 65
65 66
66 67
67 68
68 69
69 70
70 71
71 72
72 73
73 74
74 75
75 76
76 77
77 78
78 79
79 80
80 81
81 82
82 83
83 84
84 85
85 86
86 87
87 88
88 89
89 90
90 91
91 92
92 93
93 94
94 95
95 96
96 97
97 98
98 99
99 100
100 1

My OUTPUT---------->>>>

Code: Select all

3
1 4 5
99
1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
2
1 4
3
1 3 5
2
2 6
1
1
3
1 2 3
50
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99

MY Code---------->>>>>>>>>>>>

Code: Select all

#include<iostream>
#include<stack>
using namespace std;

int graph[102][102],links[102][102],flag=0,cont=0,flag1=0,highest,solution[102],not_connected_nodes;
int no_of_nodes,no_of_links;
stack<int> s;

void Initialize(int n)
{
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			links[i][j] = 5;
	highest= 0;
}

void ReIniitialize()
{
	for (int i=1;i<=no_of_nodes;i++)
		for (int j=1;j<=no_of_nodes;j++)
			graph[i][j] = links[i][j];
	flag = 0;
	flag1 = 0;
}

void printgraph(int n)
{
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
			cout<<graph[i][j];
		cout<<endl;
	}
}


int main()
{
	
	int m,n,G;
	scanf("%d",&G);//No of graphs
	while(G--)
	{
		not_connected_nodes = 0;
		scanf("%d",&no_of_nodes);
		Initialize(no_of_nodes);
		scanf("%d",&no_of_links);
		int temp=no_of_links;
		while(temp--)
		{
			scanf("%d %d\n",&m,&n);
			links[m][n]=2;
			links[n][m]=2;
		}
		for(int i=1;i<=no_of_nodes;i++)
		{
// 			cout<<"\nReInitializing\n";
			ReIniitialize();
			if(i==1)
				cont = 1;//value of count =1 
			else
				cont = not_connected_nodes + 1;
			graph[i][i] = -1;//color -1 means black
			s.push(i);
			while(!s.empty())
			{
				if(flag == 1)
					break;
				flag1=0;
				int k = s.top();
// 				cout<<"poping k--->> "<<k<<endl;
				s.pop();
				if(graph[k][k]==-1)
				{
					for(int j=1;j<=no_of_nodes;j++)
					{
						if(graph[k][j]==2)
						{
							if(graph[j][j]==-1)
							{
								flag=1;
// 								cout<<"BREAK @ "<<j<<endl;
								break;
							}
							else if(graph[j][j]==5)
							{
								graph[j][j] = 1;
// 								cout<<"\ncoloring---------------->>>  White  "<<j<<endl;
// 								printgraph(no_of_nodes);
								//sleep(1);
// 								cout<<"Pushiing "<<j<<endl;
								s.push(j);
							}
						}
					}
				}
				else//means pooping node is white
				{
					for(int a=1;a<=no_of_nodes;a++)
					{
						if(graph[k][a]==2 && graph[a][a]==5)
						{
							for(int b=1;b<=no_of_nodes;b++)
							{
								if(graph[a][b]==2)
								{
									if(graph[b][b]==-1)
									{
										flag1= 1;
// 										cout<<"BREAK @ "<<b<<endl;
										break;
									}
								}
							}
// 							cout<<"\nPushiing "<<a<<endl;
// 							cout<<"flag1 = "<<flag1<<endl;
							s.push(a);
							if(flag1 != 1)
							{
								graph[a][a] = -1;
// 								cout<<"\ncoloring---------------->>>  Black  "<<a<<endl;
// 								printgraph(no_of_nodes);
								//sleep(1);
								cont++;
							}
							else
							{
								graph[a][a] = 1;
// 								cout<<"\ncoloring---------------->>>  White  "<<a<<endl;
// 								printgraph(no_of_nodes);
								//sleep(1);
							}
						}
					}
				}
			}
			if(i==1)
			{
				for(int i=1;i<=no_of_nodes;i++)
					if(graph[i][i]==5)
						not_connected_nodes ++;
				//cout<<"not_connected_nodes "<<not_connected_nodes<<endl;
				cont += not_connected_nodes;
				//cout<<cont<<endl;
			}
			
			if(flag != 1 && cont>highest)
			{
				highest = cont;
				int c = 0;
				for(int i=1;i<=no_of_nodes;i++)
				{
					if(graph[i][i] ==-1 || graph[i][i]==5)
						solution[c++] = i;
				}
			}
		}
		cout<<highest<<endl;
		int c;
		for(c=0;c<highest-1;c++)
			cout<<solution[c]<<" ";
		cout<<solution[c]<<endl;
	}
}

If anyone able to find the error...I will be highly obliged...Thanks in advance

[vivgrn]

why would not this work?
color a vertex black.
and go down the tree coloring the vertices till all are colored according to the coloring scheme.
count the number of black vertex and number of white ones,maximum of which should be the answer.

[mf]

color a vertex black.
and go down the tree coloring the vertices

What tree? The input is a general graph.

And if your algorithm is to bicolor the graph, then it won't work even on trees.

Wrong Answer>>>>>Cant Find Any error:::

This is an NP-complete problem (maximum independent set), you should use backtracking here.

And generally, if you get WA, before trying to find errors in code, you should try to find a proof that your algorithm works correctly. And in fact that should be done before even coding.

[deadangelx]

If u dont use backtracking to solve this problem, maybe u got WA.
try this test case.
input

Code: Select all

1
12 11
1 2
3 1
4 1
5 1
6 1
7 1
8 2
9 2
10 2
11 2
12 2

output

Code: Select all

10
3 4 5 6 7 8 9 10 11 12

the graph like

Code: Select all

3   4   5       8   9  10
  \  |  /         \ | /
     1 ----------   2
  /  | \          /  \
6    7   8      11   12

And

in judge test cases, every vertex has edge(s) to other vertex(s).

Hope it helps.

[Articuno]

I am very poor in backtracking...... trying to learn...... I am getting WA again and again...... My code works for the sample inputs given here........ Can someone provide me some more test cases please? It will be very helpful. Here is my code:

Code: Select all

#include<iostream>
#include<cmath>
#include<cstring>
#include<stack>
#include<queue>
using namespace std;
#define S 110

long adj[S][S],col[S],ans1[S],ans2[S],n,m,mm,ans[S];
bool flag[S];

long dfs(long var, long c, long num)
{
	long i,j,flg=0,a1,a2,ff;
	for(i=1;i<=n;i++)
	{
		if(adj[var][i]==1 && col[i]==-1)
		{
			flag[i]=true;
			if(c==0)
			{

				col[i]=0;
				a1=dfs(i,0,num);
				col[i]=-1;

				ff=1;
				for(j=1;j<=n;j++)
				{
					if(adj[i][j]==1 && col[j]==1)
					{
						ff=0;
						break;
					}
				}
				if(ff==1)
				{
					col[i]=1;
					a2=dfs(i,1,num+1);
					col[i]=-1;
				}
				
				if(ff==0 || a1>a2) col[i]=0;
				else col[i]=1;
			}
			else
			{
				col[i]=0;
				dfs(i,0,num);
				col[i]=-1;
			}
		}
	}
	return num;
}

int main()
{
	long T,ii,i,j,a,b,n1,n2,len;
	//freopen("1.txt","r",stdin);
	scanf("%ld",&T);
	for(ii=0;ii<T;ii++)
	{
		scanf("%ld %ld",&n,&m);
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
			{
				adj[i][j]=0;
			}
		}
		for(i=0;i<m;i++)
		{
			scanf("%ld %ld",&a,&b);
			adj[a][b]=1;
			adj[b][a]=1;
		}
		for(i=1;i<=n;i++)
		{
			flag[i]=false;
		}
		len=0;
		for(a=1;a<=n;a++)
		{
			if(flag[a]==false)
			{
				flag[a]=true;
				for(i=1;i<=n;i++)
				{
					col[i]=-1;
				}
				col[a]=0;
				n1=dfs(a,0,0);
				j=0;
				for(i=1;i<=n;i++)
				{
					if(col[i]==1)
					{
						ans1[j]=i;
						j++;
					}
				}
				n1=j;

				for(i=1;i<=n;i++)
				{
					col[i]=-1;
				}
				col[a]=1;
				n2=dfs(a,1,1);
				j=0;
				for(i=1;i<=n;i++)
				{
					if(col[i]==1)
					{
						ans2[j]=i;
						j++;
					}
				}
				n2=j;

				if(n1>n2)
				{
					for(i=0;i<n1;i++)
					{
						ans[len]=ans1[i];
						len++;
					}
				}
				else
				{
					for(i=0;i<n2;i++)
					{
						ans[len]=ans2[i];
						len++;
					}
				}
			}
		}
		printf("%ld\n",len);
		for(i=0;i<len;i++)
		{
			if(i!=0) printf(" ");
			printf("%ld",ans[i]);
		}
		printf("\n");
	}
	return 0;
}

Need some help here..... thanks in advance

[chengouxuan]

is it a connected graph?

[back_tracker]

Hellow Guyssssssssssssssssssssss

it can be solved using back tracking algorithm.

1- check if u have the complete solution that is checking if you have colored all the nodes.
2- if yes, then save the information which are how many black nodes u have and what they are,
3- else, go to the next node and try to color it according to the rule, that it could be always white, but black only if there are no connected black nodes to it., (take all the possible colors for that nodes)
4- pick the first possible color, recur by going to step 1
5- then u should be able to come back to take the other possiblity of colors.

I have solved it and it works OK, but my code takes long time for some test cases, I wanna know WHY!!! and how can I iptimize my solution????


#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;

void Construct(bool c[], int &nCandidates, int edges, int **edge, int k, bool*a)
{

nCandidates=0;
bool legalblack= true;

for(int i =0; i<edges; i++)
{
if((edge[0]== k && a[edge[1]]== false ) || (edge[1]== k && a[edge[0]]== false ))
legalblack = false;

}

c[nCandidates] = true;
nCandidates++;

if(legalblack == true)
{

c[nCandidates] = false;
nCandidates++;
}
}



void back_track(vector<int> counter,vector<vector<int> > seq,int edges,int **edge, int nodes, int k,int index, bool *a, vector<int> &counterO,vector<vector<int> > &seqO, int &X)
{


bool c[2];
int nCandidates;

if(k == nodes)
{

counterO.push_back(counter[index]);


for(int j =0; j <seq[index].size(); j++)
{

seqO[X].push_back(seq[index][j]);


}

X++;


index++;
counter.push_back(0);




}

else{

k++;

Construct(c, nCandidates, edges, edge, k,a);

for(int i =0; i <nCandidates; i++)
{
a[k]= c;

if(a[k]== false)
{

counter[index]++;
seq[index].push_back(k);
}



back_track(counter,seq,edges,edge,nodes,k,index,a,counterO, seqO,X);



}
}
}




int main ()
{

int t;
cin>>t;


for(int i =0; i <t; i++)
{

int nodes;
int edges;

cin>>nodes>>edges;

int **edge = new int *[edges];

for(int i =0; i <edges; i++)
edge= new int [2];

for(int i =0; i <edges; i++)
cin>>edge[0]>>edge[1];


vector<int> counter;
counter.push_back(0);
vector<vector<int> > seq (pow(2.0,double(nodes)));

vector<int> counterO;
vector<vector<int> > seqO(pow(2.0,double(nodes)));

bool *a= new bool[nodes+1];
int X=0;
back_track(counter,seq,edges,edge,nodes,0,0,a,counterO, seqO,X);

int max =0;

for(int i =0; i <counterO.size(); i++)
{
if(counterO>max)
{
max= counterO;
}
}




for(int i =0; i <counterO.size(); i++)
{
if(counterO[i]== max)
{
cout<<counterO[i]<<endl;


for(int j =0; j <seqO[i].size(); j++)
cout<<seqO[i][j]<<" ";

cout<<endl;
break;

}
}

}

return 0;
}

//:D

[back_tracker]

Kallol, I really liked your code because it's very fast....I think your mistake is that you specify the size "105" for bool a and color. Maybe sometimes it needs more space than that, so maybe it should be moe general. good luck