193 - Graph Coloring

[NightZ-1]

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?

[junbin]

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.

[NightZ-1]

This example a fully connected graph:

Input :

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

Possible output's

1
1

1
2

1
3

1
4

1
5

My output:

1
5

It's correct... I'm crazy with this problem...

What out this in??

In:

1
1 1
1 1

[junbin]

This example a fully connected graph:

Input :

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

Possible output's

1
1

1
2

1
3

1
4

1
5

My output:

1
5

It's correct... I'm crazy with this problem...

Try this:

Code: Select all

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

Answer is 2.

[NightZ-1]

My Answer:

Your input:

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

My output:

2
1 3

Is correct??

[junbin]

My Answer:

Your input:

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

My output:

2
1 3

Is correct??

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.

[NightZ-1]

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...

[Master]

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

[sohel]

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.

[Abednego]

szymcio2001, I'm very surprised that your algorithm worked. I tried the same thing, but I repeated it 300,000 times instead of 200, and it's still WA (after 9.970 seconds). I'll try backtracking now...

[Abednego]

Oops. I had a bug in my code. It works now. ;-)

[efr_shovo]

#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;
}
}

[Malcolm]

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]

The number in 9th line should be 1.

[d91-lek]

The problem is actually Maximal Independent Set. But of course, that's NP-complete as well.

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]

The problem is actually Maximal Independent Set. But of course, that's NP-complete as well.

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.

You're absolutely right. I was a bit sloppy in what I wrote. I blame too much TV.

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?

Not sure... probably.