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

bourne
New poster
Posts: 11
Joined: Wed Jun 04, 2008 1:39 pm

Re:

Post by bourne » Thu Jun 05, 2008 12:43 pm

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

.. My AC took 0.187 seconds. 8)

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. :wink:
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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: How can i solve the problem 193

Post by Jan » Thu Jun 05, 2008 6:52 pm

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.
Ami ekhono shopno dekhi...
HomePage

bourne
New poster
Posts: 11
Joined: Wed Jun 04, 2008 1:39 pm

Re: How can i solve the problem 193

Post by bourne » Sun Jun 08, 2008 8:21 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: How can i solve the problem 193

Post by Jan » Sun Jun 08, 2008 8:39 pm

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 :wink: ).
Ami ekhono shopno dekhi...
HomePage

bourne
New poster
Posts: 11
Joined: Wed Jun 04, 2008 1:39 pm

Re: How can i solve the problem 193

Post by bourne » Sun Jun 08, 2008 8:56 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: How can i solve the problem 193

Post by Jan » Mon Jun 09, 2008 11:52 am

Make test cases and ask the admins to add them.
Ami ekhono shopno dekhi...
HomePage

dreadlord
New poster
Posts: 19
Joined: Sat Apr 19, 2008 11:19 pm

Re: How can i solve the problem 193

Post by dreadlord » Tue Jun 10, 2008 4:18 pm

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
New poster
Posts: 19
Joined: Mon Jul 28, 2008 7:00 pm
Location: India

Re: How can i solve the problem 193

Post by empo » Fri Dec 12, 2008 4:38 pm

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
"Accepted" is my passion but RTE is my weakness.....

vivgrn
New poster
Posts: 6
Joined: Sat Aug 25, 2007 4:48 pm

Re: How can i solve the problem 193

Post by vivgrn » Tue Dec 30, 2008 9:00 am

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: How can i solve the problem 193

Post by mf » Tue Dec 30, 2008 10:20 am

vivgrn wrote: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.
empo wrote: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
New poster
Posts: 32
Joined: Tue Feb 13, 2007 1:31 pm

Re: How can i solve the problem 193

Post by deadangelx » Fri Apr 17, 2009 11:34 pm

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
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: How can i solve the problem 193

Post by Articuno » Thu Dec 24, 2009 8:21 am

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 :)
May be tomorrow is a better day............ :)

chengouxuan
New poster
Posts: 10
Joined: Wed Dec 15, 2010 12:32 pm

Re: 193 Graph Coloring

Post by chengouxuan » Sat Mar 19, 2011 8:48 am

is it a connected graph?

back_tracker
New poster
Posts: 9
Joined: Sun Jun 19, 2011 12:03 am

Re: 193 Graph Coloring

Post by back_tracker » Sun Jun 19, 2011 12:10 am

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
New poster
Posts: 9
Joined: Sun Jun 19, 2011 12:03 am

Re: 193 Graph Coloring

Post by back_tracker » Sun Jun 19, 2011 8:46 pm

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

Post Reply

Return to “Volume 1 (100-199)”