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

NightZ-1
New poster
Posts: 8
Joined: Sun Feb 01, 2004 11:47 pm
Location: SP, Brazil
Contact:

Post by NightZ-1 » Fri Apr 02, 2004 5:23 am

I use this algo, but I get WA, :evil:
[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
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Fri Apr 02, 2004 2:46 pm

NightZ-1 wrote:I use this algo, but I get WA, :evil:
[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
New poster
Posts: 8
Joined: Sun Feb 01, 2004 11:47 pm
Location: SP, Brazil
Contact:

Post by NightZ-1 » Fri Apr 02, 2004 5:10 pm

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

What out this in??

In:
1
1 1
1 1

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Fri Apr 02, 2004 6:01 pm

NightZ-1 wrote: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... :evil:

Try this:

Code: Select all

1
4 5
1 2
2 3
3 4
1 4
2 4
Answer is 2.

NightZ-1
New poster
Posts: 8
Joined: Sun Feb 01, 2004 11:47 pm
Location: SP, Brazil
Contact:

Post by NightZ-1 » Fri Apr 02, 2004 7:03 pm

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
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Sat Apr 03, 2004 3:45 pm

NightZ-1 wrote: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
New poster
Posts: 8
Joined: Sun Feb 01, 2004 11:47 pm
Location: SP, Brazil
Contact:

Post by NightZ-1 » Sat Apr 03, 2004 11:49 pm

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

Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

How can i solve the problem 193

Post by Master » Sat Aug 21, 2004 9:13 am

I have tried this problem very much but can't find any good algorithm :o . can anyone give me a algorithm for this problem.

Thanks in advance
M H Rasel
CUET Old Sailor

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Sat Aug 21, 2004 1:41 pm

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.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Wed Oct 06, 2004 4:03 am

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...
If only I had as much free time as I did in college...

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Wed Oct 06, 2004 4:14 am

Oops. I had a bug in my code. It works now. ;-)
If only I had as much free time as I did in college...

efr_shovo
New poster
Posts: 38
Joined: Wed Sep 22, 2004 9:09 am

193 why it gives worng ans? Pleazzz Help

Post by efr_shovo » Thu Oct 14, 2004 4:49 pm

#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
New poster
Posts: 5
Joined: Fri Jan 23, 2004 4:34 pm
Location: Taiwan

Re: no match

Post by Malcolm » Wed Oct 27, 2004 8:28 pm

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]
The number in 9th line should be 1.

d91-lek
New poster
Posts: 22
Joined: Thu Sep 16, 2004 2:25 am
Location: KTH, Stockholm
Contact:

Post by d91-lek » Mon Dec 13, 2004 9:14 pm

Per wrote: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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Tue Dec 14, 2004 11:54 am

d91-lek wrote:
Per wrote: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. :)

Post Reply

Return to “Volume 1 (100-199)”