### problem no 193

Posted:

**Sat Jun 01, 2002 5:30 am**what is the output of the following input

1

3 2

1 2

1 3

1

3 2

1 2

1 3

Page **1** of **7**

Posted: **Sat Jun 01, 2002 5:30 am**

what is the output of the following input

1

3 2

1 2

1 3

1

3 2

1 2

1 3

Posted: **Thu Jun 27, 2002 3:37 pm**

Hi!

For this test case the answer is :

2

2 3

(these nodes can be colored black because they are not directly connected)

Good Luck

For this test case the answer is :

2

2 3

(these nodes can be colored black because they are not directly connected)

Good Luck

Posted: **Mon Jul 15, 2002 5:27 am**

My algorithem is ...

Form the minimum degree node to the maxmum degree node,

if its all neighbors are not black,it is going to be colored.

Is it wrong ...??...

I can got correct results in many cases,but I got WA,WA,and WA...

Form the minimum degree node to the maxmum degree node,

if its all neighbors are not black,it is going to be colored.

Is it wrong ...??...

I can got correct results in many cases,but I got WA,WA,and WA...

Posted: **Wed Jul 31, 2002 1:37 pm**

Nice heuristic, but nothing more than that...

Can you PROOF your algorithm is correct?

Can you PROOF your algorithm is correct?

Posted: **Fri Aug 02, 2002 5:48 pm**

Sorry,I can't proof.....

This method broke into my heart occasionally.

I just don't know why it's wrong...^^....

Ex.

1

6 8

1 2

1 3

2 4

2 5

3 4

3 6

4 6

5 6

Step 1. Construct all neighbors for each node

node neighbors degree can_be_color

1 2 3 2 true

2 1 4 5 3 true

3 1 4 6 3 true

4 2 3 6 3 true

5 2 6 2 true

6 3 4 5 3 true

Step 2. Start from the node which has lowest degree.

The lowest degree in this case is "2"

So,we search from node 1 to node 6 to find the node which can be

colored and has degree "2"....we get node "1" , so all neighbors of

node 1 can not be colored...

node neighbors degree can_be_color

1 2 3 2 "colored"

2 1 4 5 3 "false forever"

3 1 4 6 3 "false forever"

4 2 3 6 3 true

5 2 6 2 true

6 3 4 5 3 true

Then we get node 5 which can be colored and has degree "2",so all

neighbors of node 5 can not be colored....

node neighbors degree can_be_color

1 2 3 2 "colored 1 "

2 1 4 5 3 "false forever"

3 1 4 6 3 "false forever"

4 2 3 6 3 true

5 2 6 2 "colored 2 "

6 3 4 5 3 "false forever"

Step 3. Now we have finished all node having degree 2,so we go to

degree 3..

We find node 4 can be colored and has degree "3",so we select it and

find that all node have been considered..............

node neighbors degree can_be_color

1 2 3 2 "colored 1 "

2 1 4 5 3 "false forever"

3 1 4 6 3 "false forever"

4 2 3 6 3 "colored 3 "

5 2 6 2 "colored 2 "

6 3 4 5 3 "false forever"

So the answer is

3

1 4 5

This method broke into my heart occasionally.

I just don't know why it's wrong...^^....

Ex.

1

6 8

1 2

1 3

2 4

2 5

3 4

3 6

4 6

5 6

Step 1. Construct all neighbors for each node

node neighbors degree can_be_color

1 2 3 2 true

2 1 4 5 3 true

3 1 4 6 3 true

4 2 3 6 3 true

5 2 6 2 true

6 3 4 5 3 true

Step 2. Start from the node which has lowest degree.

The lowest degree in this case is "2"

So,we search from node 1 to node 6 to find the node which can be

colored and has degree "2"....we get node "1" , so all neighbors of

node 1 can not be colored...

node neighbors degree can_be_color

1 2 3 2 "colored"

2 1 4 5 3 "false forever"

3 1 4 6 3 "false forever"

4 2 3 6 3 true

5 2 6 2 true

6 3 4 5 3 true

Then we get node 5 which can be colored and has degree "2",so all

neighbors of node 5 can not be colored....

node neighbors degree can_be_color

1 2 3 2 "colored 1 "

2 1 4 5 3 "false forever"

3 1 4 6 3 "false forever"

4 2 3 6 3 true

5 2 6 2 "colored 2 "

6 3 4 5 3 "false forever"

Step 3. Now we have finished all node having degree 2,so we go to

degree 3..

We find node 4 can be colored and has degree "3",so we select it and

find that all node have been considered..............

node neighbors degree can_be_color

1 2 3 2 "colored 1 "

2 1 4 5 3 "false forever"

3 1 4 6 3 "false forever"

4 2 3 6 3 "colored 3 "

5 2 6 2 "colored 2 "

6 3 4 5 3 "false forever"

So the answer is

3

1 4 5

Posted: **Fri Aug 02, 2002 5:53 pm**

Sorry,I can't proof.....

This method broke into my heart occasionally.

I just don't know why it's wrong...^^....

Ex.

1

6 8

1 2

1 3

2 4

2 5

3 4

3 6

4 6

5 6

Step 1. Construct all neighbors for each node

node neighbors degree can_be_color

1 2 3 2 true

2 1 4 5 3 true

3 1 4 6 3 true

4 2 3 6 3 true

5 2 6 2 true

6 3 4 5 3 true

Step 2. Start from the node which has lowest degree.

The lowest degree in this case is "2"

So,we search from node 1 to node 6 to find the node which can be

colored and has degree "2"....we get node "1" , so all neighbors of

node 1 can not be colored...

node neighbors degree can_be_color

1 2 3 2 "colored"

2 1 4 5 3 "false forever"

3 1 4 6 3 "false forever"

4 2 3 6 3 true

5 2 6 2 true

6 3 4 5 3 true

Then we get node 5 which can be colored and has degree "2",so all

neighbors of node 5 can not be colored....

node neighbors degree can_be_color

1 2 3 2 "colored 1 "

2 1 4 5 3 "false forever"

3 1 4 6 3 "false forever"

4 2 3 6 3 true

5 2 6 2 "colored 2 "

6 3 4 5 3 "false forever"

Step 3. Now we have finished all node having degree 2,so we go to

degree 3..

We find node 4 can be colored and has degree "3",so we select it and

find that all node have been considered..............

node neighbors degree can_be_color

1 2 3 2 "colored 1 "

2 1 4 5 3 "false forever"

3 1 4 6 3 "false forever"

4 2 3 6 3 "colored 3 "

5 2 6 2 "colored 2 "

6 3 4 5 3 "false forever"

So the answer is

3

1 4 5

This method broke into my heart occasionally.

I just don't know why it's wrong...^^....

Ex.

1

6 8

1 2

1 3

2 4

2 5

3 4

3 6

4 6

5 6

Step 1. Construct all neighbors for each node

node neighbors degree can_be_color

1 2 3 2 true

2 1 4 5 3 true

3 1 4 6 3 true

4 2 3 6 3 true

5 2 6 2 true

6 3 4 5 3 true

Step 2. Start from the node which has lowest degree.

The lowest degree in this case is "2"

So,we search from node 1 to node 6 to find the node which can be

colored and has degree "2"....we get node "1" , so all neighbors of

node 1 can not be colored...

node neighbors degree can_be_color

1 2 3 2 "colored"

2 1 4 5 3 "false forever"

3 1 4 6 3 "false forever"

4 2 3 6 3 true

5 2 6 2 true

6 3 4 5 3 true

Then we get node 5 which can be colored and has degree "2",so all

neighbors of node 5 can not be colored....

node neighbors degree can_be_color

1 2 3 2 "colored 1 "

2 1 4 5 3 "false forever"

3 1 4 6 3 "false forever"

4 2 3 6 3 true

5 2 6 2 "colored 2 "

6 3 4 5 3 "false forever"

Step 3. Now we have finished all node having degree 2,so we go to

degree 3..

We find node 4 can be colored and has degree "3",so we select it and

find that all node have been considered..............

node neighbors degree can_be_color

1 2 3 2 "colored 1 "

2 1 4 5 3 "false forever"

3 1 4 6 3 "false forever"

4 2 3 6 3 "colored 3 "

5 2 6 2 "colored 2 "

6 3 4 5 3 "false forever"

So the answer is

3

1 4 5

Posted: **Sun Aug 11, 2002 6:49 pm**

/*@BEGIN_OF_SOURCE_CODE*/

#include<stdio.h>

#include<stdlib.h>

#define BLACK 2

#define WHITE 1

int vertex[102][102];

int flag[102],x[102],max,vertx;

void Coloring(int i,int count)

{

int j;

if(i==vertx){

if(max<count){

max =count;

for(j=0;j<vertx;j++)

if(flag[j]==BLACK) x[j] =1;

else x[j] = 0;

}

return;

}

for(j=0;j<vertx;j++)

if(vertex*[j] == 1 && flag[j] == BLACK) break;*

if(j==vertx){

flag* =BLACK;*

Coloring(i+1,count+1);

flag* = 0;*

}

else{

flag* = WHITE;*

Coloring(i+1,count);

flag* = 0;*

}

}

int main()

{

int edge,n,i,j,a,b,count;

scanf("%d",&n);

while(n-->0){

scanf("%d%d",&vertx,&edge);

max = 0;

for(i=0;i<vertx;i++) {

flag* = 0,x** = 0;*

for(j = 0;j<vertx;j++)

vertex*[j] = 0;*

}

for(i=0;i<edge;i++){

scanf("%d%d",&a,&b);

vertex[a-1][b-1]=vertex[b-1][a-1]=1;

}

for(i =0 ;i<vertx;i++)

Coloring(i,0);

printf("%d\n",max);

for(i=0;i<vertx;i++)

if(x* == 1) printf("%d ",i+1);*

printf("\n");

}

return 0;

}

/*@END_OF_SOURCE_CODE*/

*******

Is the algorithm right?

Can anyone help me?

#include<stdio.h>

#include<stdlib.h>

#define BLACK 2

#define WHITE 1

int vertex[102][102];

int flag[102],x[102],max,vertx;

void Coloring(int i,int count)

{

int j;

if(i==vertx){

if(max<count){

max =count;

for(j=0;j<vertx;j++)

if(flag[j]==BLACK) x[j] =1;

else x[j] = 0;

}

return;

}

for(j=0;j<vertx;j++)

if(vertex

if(j==vertx){

flag

Coloring(i+1,count+1);

flag

}

else{

flag

Coloring(i+1,count);

flag

}

}

int main()

{

int edge,n,i,j,a,b,count;

scanf("%d",&n);

while(n-->0){

scanf("%d%d",&vertx,&edge);

max = 0;

for(i=0;i<vertx;i++) {

flag

for(j = 0;j<vertx;j++)

vertex

}

for(i=0;i<edge;i++){

scanf("%d%d",&a,&b);

vertex[a-1][b-1]=vertex[b-1][a-1]=1;

}

for(i =0 ;i<vertx;i++)

Coloring(i,0);

printf("%d\n",max);

for(i=0;i<vertx;i++)

if(x

printf("\n");

}

return 0;

}

/*@END_OF_SOURCE_CODE*/

*******

Is the algorithm right?

Can anyone help me?

Posted: **Mon Sep 30, 2002 11:07 am**

Hello,

I tried to solve 193 (and got AC in 0.01s), but I'm using some kind of probabilistic approach: I randomly select a node, remove it and its neighbours until there are no nodes left. I repeat this several times (100 is enough) to get the maximum node count.

I know that this problem (Maximum Independent Set) is NP-complete, but is there another (maybe a bit more deterministic) solution?

I tried to solve 193 (and got AC in 0.01s), but I'm using some kind of probabilistic approach: I randomly select a node, remove it and its neighbours until there are no nodes left. I repeat this several times (100 is enough) to get the maximum node count.

I know that this problem (Maximum Independent Set) is NP-complete, but is there another (maybe a bit more deterministic) solution?

Posted: **Sun Jan 19, 2003 8:13 pm**

i used the following heuristic to solve the problem:

find the node with minimum degree put it in the solution vector and delete it and all the nodes connected to it and so on till u finish all the nodes.

it generates the right answer for the test cases so can any body points out what is wrong with this algorithm and give me some difficult test cases, thanks.

find the node with minimum degree put it in the solution vector and delete it and all the nodes connected to it and so on till u finish all the nodes.

it generates the right answer for the test cases so can any body points out what is wrong with this algorithm and give me some difficult test cases, thanks.

Code: Select all

```
[cpp]
#include<iostream>
#include<fstream>
using namespace std;
int findmin();
void adjust(int x);
int a[101]={-1};
int b[101][101]={0};
int n;
int main()
{
//ifstream ins;
//ins.open("in.txt");
//cin=ins;
int m,k;
int temp1,temp2;
int f,t;
int count;
cin>>m;
for(t=1;t<=m;t++)
{
count=0;
//initialize a,b
cin>>n>>k;
for(f=1; f<=n;f++)
{
//a[f]=-1;
for(int c=1;c<=n;c++)
b[f][c]=0;
}
for(f=1;f<=k;f++)
{
cin>>temp1>>temp2;
if(temp1 !=temp2)
{
b[temp1][temp2]=1;
b[temp2][temp1]=1;
}
}
for(f=1;f<=n;f++)
{
int y=findmin();
if(y>n)
break;
a[f]=y;
count++;
for(int t=1;t<=n;t++)
{
if(b[y][t]==1)
adjust(t);
}
adjust(y);
}
cout<<count<<endl;
for(f=1;f<=count;f++)
{if(f==count)
cout<<a[f];
else
cout<<a[f]<<" ";
}
cout<<endl;
}
return 0;
}
int findmin()
{
int index=1000;
int count;
int mincount=1000;
int i,j;
for(i=1;i<=n;i++)
{
count=0;
for(j=1;j<=n;j++)
{
if(b[i][j]==-1)
break;
if(b[i][j])
count++;
}
if(j>n && count<mincount)
{
mincount=count;
index=i;
}
}
return index;
}
void adjust(int x)
{
for(int i=1;i<=n;i++)
{
if(b[i][x]==1)
b[i][x]=0;
b[x][i]=-1;
}
}
[/cpp]
```

Posted: **Mon Jan 20, 2003 7:36 pm**

so far as i know this algorithm will generate a **maximal** independent set, not necessarily the one that has **maximum** size.

maximal set: no other maximal set contains it

maximum set: the set whose cardinality is maximum

maximal set: no other maximal set contains it

maximum set: the set whose cardinality is maximum

Posted: **Wed Feb 12, 2003 10:51 pm**

Hi,

Can anyone provide their solution to the graph coloring problem and the source code(c,c++ or java). I'm working on a problem where I need this solution.

Thanks.

Can anyone provide their solution to the graph coloring problem and the source code(c,c++ or java). I'm working on a problem where I need this solution.

Thanks.

Posted: **Wed Jul 16, 2003 4:49 am**

I didnt think a greedy algorithm would work... so is this problem NP-Complete. any kool algorithms? I was looking at Lawler's algorithm...

Posted: **Sat Oct 25, 2003 2:35 am**

Can anyone tell me some inputs and outputs?

Posted: **Sun Oct 26, 2003 1:38 pm**

not if you don't provide us with some details about your program, algorithm, or implementation

Posted: **Sun Oct 26, 2003 2:02 pm**

Code: Select all

```
for(i=1;i<=node;i++)
{
temp=graph
dfs(i)
}
```

Finally, took the maximum number of Black nodes from the dfs(1->node)

is it, ok?