193  Graph Coloring
Moderator: Board moderators
I use this algo, but I get WA,
[c]TColors vertexColor(TVertex *vertex)
{
TEdge *edge;
edge = vertex>edges.first;
while ( edge ){
if ( edge>dest>color == clBlack )
return clWhite;
edge = edge>next;
}
return clBlack;
};
void makeColors(TGraph *graph, int start)
{
TVertex *vertex;
TEdge *edge;
vertex = searchVertex(graph, start);
vertex>visit = true;
edge = vertex>edges.first;
while ( edge ){
if ( !edge>dest>visit )
makeColors(graph, edge>dest>num);
edge = edge>next;
}
vertex>color = vertexColor(vertex);
if ( vertex>color == clBlack )
graph>black++;
};[/c]
Where it is my error?
[c]TColors vertexColor(TVertex *vertex)
{
TEdge *edge;
edge = vertex>edges.first;
while ( edge ){
if ( edge>dest>color == clBlack )
return clWhite;
edge = edge>next;
}
return clBlack;
};
void makeColors(TGraph *graph, int start)
{
TVertex *vertex;
TEdge *edge;
vertex = searchVertex(graph, start);
vertex>visit = true;
edge = vertex>edges.first;
while ( edge ){
if ( !edge>dest>visit )
makeColors(graph, edge>dest>num);
edge = edge>next;
}
vertex>color = vertexColor(vertex);
if ( vertex>color == clBlack )
graph>black++;
};[/c]
Where it is my error?
NightZ1 wrote:I use this algo, but I get WA,
[c]TColors vertexColor(TVertex *vertex)
{
TEdge *edge;
edge = vertex>edges.first;
while ( edge ){
if ( edge>dest>color == clBlack )
return clWhite;
edge = edge>next;
}
return clBlack;
};
void makeColors(TGraph *graph, int start)
{
TVertex *vertex;
TEdge *edge;
vertex = searchVertex(graph, start);
vertex>visit = true;
edge = vertex>edges.first;
while ( edge ){
if ( !edge>dest>visit )
makeColors(graph, edge>dest>num);
edge = edge>next;
}
vertex>color = vertexColor(vertex);
if ( vertex>color == clBlack )
graph>black++;
};[/c]
Where it is my error?
I think your algo will fail for fully connected graphs.
NightZ1 wrote:This example a fully connected graph:
Input :Possible output's1
5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5My output:1
1
1
2
1
3
1
4
1
5It's correct... I'm crazy with this problem...1
5
Try this:
Code: Select all
1
4 5
1 2
2 3
3 4
1 4
2 4
NightZ1 wrote:My Answer:
Your input:My output:1
4 5
1 2
2 3
3 4
1 4
2 4Is correct??2
1 3
Draw out the graph.. do a manual trace.. as far as I can tell from your snippet of code, there can exist a case where:
(using the above graph)
You start from node 1, go to 2, go to 3, go to 4. Since 4 is connected to both 1, 2 and 3, and all of them are visited, but none of them are coloured, 4 is coloured black. 3 is then coloured white (since it touches 4). 2 is then coloured white (since it touches 4) and 1 is then coloured white (since it touches 4).
Without the complete code, it is hard to guess how you order your graph and then come up with a definite counter example, but if you permute all difference possibilities of the graph above, you should find a case where you fall into the trap I discribed above.
This is my code, for search of the max black nodes, starting for all nodes:
[c]initList(&list);
for ( i = 0; i < vertices; i++ ){
cleanGraph(&graph);
makeColors(&graph, (i+1));
vertex = graph.first;
while ( vertex ){
if ( !vertex>visit )
makeColors(&graph, vertex>num);
vertex = vertex>next;
}
if ( graph.black > list.count ){
destroyList(&list);
initList(&list);
vertex = graph.first;
while ( vertex ){
if ( vertex>color == clBlack )
addList(&list, vertex);
vertex = vertex>next;
}
}
}[/c]
But, I get ever WA...
[c]initList(&list);
for ( i = 0; i < vertices; i++ ){
cleanGraph(&graph);
makeColors(&graph, (i+1));
vertex = graph.first;
while ( vertex ){
if ( !vertex>visit )
makeColors(&graph, vertex>num);
vertex = vertex>next;
}
if ( graph.black > list.count ){
destroyList(&list);
initList(&list);
vertex = graph.first;
while ( vertex ){
if ( vertex>color == clBlack )
addList(&list, vertex);
vertex = vertex>next;
}
}
}[/c]
But, I get ever WA...

 Learning poster
 Posts: 82
 Joined: Thu Oct 10, 2002 1:15 pm
 Location: St. Johns, Canada
 Contact:
How can i solve the problem 193
I have tried this problem very much but can't find any good algorithm . can anyone give me a algorithm for this problem.
Thanks in advance
M H Rasel
CUET Old Sailor
Thanks in advance
M H Rasel
CUET Old Sailor
Backtracking with pruning should be enough to pass the time limit.
My AC took 0.187 seconds.
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.
My AC took 0.187 seconds.
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.
193 why it gives worng ans? Pleazzz Help
#include<stdio.h>
#define MAX 100
#define white 0
#define black 1
long m;
long n,k;
int AdjMat[MAX][MAX];
int Color[MAX];
int Visit[MAX];
int Node[MAX];
long i,g,j,l,a,b,ColorNum;
int GraphColor(int u)
{
Visit=1;
if(Color)
ColorNum++;
if(u==n)
return 0;
for(int v=1;v<=n;v++)
{
if(AdjMat[v]!=0)
{
if(Visit[v]!=1)
{
if(Color)
{
Color[v]=white;
}
}
}
}
GraphColor(++u);
return 0;
}
void main()
{
scanf("%ld",&m);
for(i=0;i<m;i++)
{
scanf("%ld %ld",&n,&k);
for(j=1;j<=n;j++)
{
for(l=1;l<=n;l++)
AdjMat[j][l]=0;
Color[j]=black;
}
for(j=1;j<=k;j++)
{
scanf("%ld %ld",&a,&b);
AdjMat[a]=1;
}
GraphColor(1);
printf("%ld\n",ColorNum);
for(g=1;g<=n;g++)
{
if(Color[g])
printf("%ld ",g);
Visit[g]=0;
}
printf("\n");
ColorNum=0;
}
}
#define MAX 100
#define white 0
#define black 1
long m;
long n,k;
int AdjMat[MAX][MAX];
int Color[MAX];
int Visit[MAX];
int Node[MAX];
long i,g,j,l,a,b,ColorNum;
int GraphColor(int u)
{
Visit=1;
if(Color)
ColorNum++;
if(u==n)
return 0;
for(int v=1;v<=n;v++)
{
if(AdjMat[v]!=0)
{
if(Visit[v]!=1)
{
if(Color)
{
Color[v]=white;
}
}
}
}
GraphColor(++u);
return 0;
}
void main()
{
scanf("%ld",&m);
for(i=0;i<m;i++)
{
scanf("%ld %ld",&n,&k);
for(j=1;j<=n;j++)
{
for(l=1;l<=n;l++)
AdjMat[j][l]=0;
Color[j]=black;
}
for(j=1;j<=k;j++)
{
scanf("%ld %ld",&a,&b);
AdjMat[a]=1;
}
GraphColor(1);
printf("%ld\n",ColorNum);
for(g=1;g<=n;g++)
{
if(Color[g])
printf("%ld ",g);
Visit[g]=0;
}
printf("\n");
ColorNum=0;
}
}
Re: no match
The number in 9th line should be 1.sohel wrote:My AC program gives the following output for your input:
[c]
3
1 4 5
5
1 5 6 7 9
7
1 5 6 8 9 10 12
6
1 5 6 10 12 14
0
1
2
1 3
2
1 3
3
1 3 5
2
1 3
2
1 3
3
2 4 7
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
11
1 2 3 6 7 8 9 11 15 16 20
7
1 6 7 8 9 10 11
24
1 5 7 8 9 10 11 15 16 17 18 19 20 21 22 23 24 25 27 28 29 31 34 35
[/c]
Cormen, Leiserson, Rivest say you should not confuse Maximal Set with Maximum Set. Maximal Set being just an independent set which can't grow more. I solved 193  Maximum Independent Set  by taking the biggest of 200 randomly started maximal sets. After a few submits the seed was with me. Should I blush now?Per wrote:The problem is actually Maximal Independent Set. But of course, that's NPcomplete as well.
You're absolutely right. I was a bit sloppy in what I wrote. I blame too much TV.d91lek wrote:Cormen, Leiserson, Rivest say you should not confuse Maximal Set with Maximum Set. Maximal Set being just an independent set which can't grow more.Per wrote:The problem is actually Maximal Independent Set. But of course, that's NPcomplete as well.
Not sure... probably.I solved 193  Maximum Independent Set  by taking the biggest of 200 randomly started maximal sets. After a few submits the seed was with me. Should I blush now?