Page **3** of **7**

Posted: **Fri Apr 02, 2004 5:23 am**

by **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?

Posted: **Fri Apr 02, 2004 2:46 pm**

by **junbin**

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

Posted: **Fri Apr 02, 2004 5:10 pm**

by **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

Posted: **Fri Apr 02, 2004 6:01 pm**

by **junbin**

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

Try this:

Answer is 2.

Posted: **Fri Apr 02, 2004 7:03 pm**

by **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??

Posted: **Sat Apr 03, 2004 3:45 pm**

by **junbin**

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.

Posted: **Sat Apr 03, 2004 11:49 pm**

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

### How can i solve the problem 193

Posted: **Sat Aug 21, 2004 9:13 am**

by **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

Posted: **Sat Aug 21, 2004 1:41 pm**

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

Posted: **Wed Oct 06, 2004 4:03 am**

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

Posted: **Wed Oct 06, 2004 4:14 am**

by **Abednego**

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

### 193 why it gives worng ans? Pleazzz Help

Posted: **Thu Oct 14, 2004 4:49 pm**

by **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;

}

}

### Re: no match

Posted: **Wed Oct 27, 2004 8:28 pm**

by **Malcolm**

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.

Posted: **Mon Dec 13, 2004 9:14 pm**

by **d91-lek**

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?

Posted: **Tue Dec 14, 2004 11:54 am**

by **Per**

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.