193 - Graph Coloring

[geran]

I get WA on problem 193 and cant figure out why. Im testing my solution with input:

Code: Select all

4
6 8
1 2
1 3
2 4
2 5
3 4
3 6
4 6
5 6
4 5
1 2
1 3
1 4
2 3
2 4
3 2
1 2
1 3
3 2
1 2
2 3

graphs
and get's output:

Code: Select all

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

The output is correct (I think ) on my small graphs. Can somebody please give me a larger graph and the output of you AC solution.

[geran]

by the way, the alg. Im using goes something like this...

find the lowest degree vertex, add it to the independent set and delete it and all vertices adjancent to it from the graph, repeate untill graph G is empty.

[geran]

I have realised the the algorith I used before will not work an all graph's so I tried to choose a random node, add it to the set, delelet all nodes connected to it while there is still some nodes left, such approch is suggested here

But I cant get it to work, I think I dont choose a node so random, can somebody please help me. Here is my code:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define INF 1000000

typedef struct {
	int nedges;
	int *edges;
} Node;

Node* graph;
Node* g;
int* colored;
int* cnodes;

int main() {
	int i, j, m, r, s, q, p, numgraph, n, k, n1 = 0, n2 = 0, cnode = 0, num = 0, ncolors = 0, rn = 0, empty = 0;
	/*read how many graphs/test case's in this input*/
	if(scanf("%d", &numgraph) == EOF) { exit(-1); }
	/*for all test case's*/
	for(i = 0; i < numgraph; i++) {
		/*read n k for this graph*/
		if(scanf("%d %d", &n, &k) == EOF) { exit(-1); }
		/*allocate mem for n nodes*/
		if((graph = (Node*)malloc(sizeof(Node)*n)) == NULL)
		{ fprintf(stderr, "Malloc Error!\n"); exit(-1); }
		memset(graph,0,sizeof(Node)*n);

		if((g = (Node*)malloc(sizeof(Node)*n)) == NULL)
		{ fprintf(stderr, "Malloc Error!\n"); exit(-1); }
		memset(g,0,sizeof(Node)*n);
		/*allocate mem for result*/
		if((colored = (int*)malloc(sizeof(int)*n)) == NULL)
		{ fprintf(stderr, "Malloc Error!\n"); exit(-1); }
		memset(colored,0,sizeof(int)*n);
		
		/*allcate mem for neigbour list at nodes*/
		for(j = 0; j < n; j++) {
			if((graph[j].edges = (int*)malloc(sizeof(int)*n)) == NULL)
			{ fprintf(stderr, "Malloc Error!\n"); exit(-1); }
			memset(graph[j].edges,0,sizeof(int)*n);
			graph[j].nedges = 0;

			if((g[j].edges = (int*)malloc(sizeof(int)*n)) == NULL)
			{ fprintf(stderr, "Malloc Error!\n"); exit(-1); }
			memset(g[j].edges,0,sizeof(int)*n);
			g[j].nedges = 0;
		}
		/*add edges..*/
		for(j = 0; j < k; j++) {
			if(scanf("%d %d", &n1, &n2) == EOF) { exit(-1); }
			graph[n1-1].edges[n2-1] = 1;
			graph[n1-1].nedges++;
			graph[n2-1].edges[n1-1] = 1;
			graph[n2-1].nedges++;
		}	
		
		/*find Maximal Independent Set*/
		num = 0;
		cnodes = malloc(sizeof(int)*n);
		for(q = 0; q < 500; q++) {	
			/*copy graph to g*/
			for(j = 0; j < n; j++) {
				memcpy(g[j].edges,graph[j].edges,sizeof(int)*n);
				g[j].nedges = graph[j].nedges;
			}
			ncolors = 0;
			for(p = 0; p < n; p++) {	
				cnode = 0;
				s = 0;
				memset(cnodes,0,sizeof(int)*n);
				/*find all nodes that is not removed from g*/
				for(j = 0; j < n; j++) {
					if(g[j].nedges != INF) {
						cnodes[s] = j+1;
						s++;
					}
				}
				if(s != 0) {
					srand(q*p+time(0));
					rn = rand()%s;
					cnode = cnodes[rn];
					ncolors++;
					/*add cnode to set I ...*/

					/*remove cnode and its neigbours...*/
					for(m = 0; m < n; m++) {
						if(g[cnode-1].edges[m] == 1) {
							g[m].nedges = INF;
							g[cnode-1].edges[m] = 0;
							g[m].edges[cnode-1] = 0;
							for(r = 0; r < n; r++) {
								if(g[m].edges[r] == 1) {
									g[r].edges[m] = 0;
								}
							}
						}
					}
					g[cnode-1].nedges = INF;
					/*update degree*/
					for(m = 0; m < n; m++) {
						if(g[m].nedges != INF) {
							g[m].nedges = 0;
							for(r = 0; r < n; r++) {
								if(g[m].edges[r] == 1) {
									g[m].nedges++;
								}
							}
						}
					}
					/*and repeate till g is empty*/
				}
			}
			//printf("q:= %d ncolors:= %d\n",q,ncolors);
			if(num < ncolors) {
				num = ncolors;
			}
		}
		
		/*output result*/
		printf("%d\n", num);
		/*free graph*/
		for(j = 0; j < n; j++) {
			free(graph[j].edges);
			free(g[j].edges);
		}
		free(graph);
		free(g);
		free(cnodes);
		free(colored);
		/*reset vars*/
		n1 = 0; n2 = 0;
	}
	return 1;
}

[mf]

Your program is expected to print both the number of black vertices, and the list of these vertices too.

srand(q*p+time(0));
rn = rand()%s;

You should call srand() only once, at the beginning of main(), but not every time you need another random number.

[geran]

I know that my app should both print the nodes and number of black vertices, I trying to get the number of black vertices correct first.

[MD. OMAR FARUQUE]

IT IS A GRAPH PROBLEM.
I AM WEAK IN GRAPH . HOW I CAN I SOLVE IT. HAVE ANYBODY TO HELP ME.

[asif_rahman0]

someone help me.
why i am getting wrong answer?? where i am wrong?? I used two bfs() to find
the maximum number of blacks for coloring.

Code: Select all

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define NOD	210
#define INF	1<<30
bool mat[NOD][NOD];
using namespace std;
int node,edge;
int main()
{
	int x,y,i,j,tst;
	cin>>tst;
	while(tst--){
		cin>>node;
		cin>>edge;
		if(!node) break;
		for(i=0;i<edge;i++){
			cin>>x>>y;
			mat[x][y]=true;
			mat[y][x]=true;
		}
		queue<int> q;
		int color1[210],color2[210];
		for(i=1;i<=node;i++) color1[i]=INF;
		q.push(1);
		color1[q.front()]=1;
		while(!q.empty()){
			int temp=q.front();
			q.pop();
			for(i=1;i<=node;i++){
				if(mat[temp][i]==true){
					if(color1[i]==INF||color1[i]==1){
						if(color1[temp]==1) color1[i]=2;
						else if(color1[temp]==2) color1[i]=1;
						q.push(i);
					}
				}
			}
		}
		int max1;
		max1=0;
		for(i=1;i<=node;i++) if(color1[i]==1||color1[i]==INF) max1++;
		for(i=1;i<=node;i++) color2[i]=INF;
		q.push(1);
		color2[q.front()]=2;
		while(!q.empty()){
			int temp=q.front();
			q.pop();
			for(i=1;i<=node;i++){
				if(mat[temp][i]==true){
					if(color2[i]==INF||color2[i]==1){
						if(color2[temp]==1) color2[i]=2;
						else if(color2[temp]==2) color2[i]=1;
						q.push(i);
					}
				}
			}
		}
		int max2;
		max2=0;
		for(i=1;i<=node;i++) if(color2[i]==1||color2[i]==INF) max2++;
		if(max2>max1){
			cout<<max2<<endl;
			for(i=1;i<=node;i++) if(color2[i]==1||color2[i]==INF) cout<<i<<' ';
			cout<<endl;
		}
		else{
			cout<<max1<<endl;
			for(i=1;i<=node;i++){
				if(color1[i]==1||color1[i]==INF) cout<<i<<' ';
			}
			cout<<endl;
		}
		for(i=1;i<=node;i++) for(j=1;j<=node;j++) mat[i][j]=false;
	}
	return 0;
}

help would be appreciated.

bye
rabbi

[anne0604]

I use the testcase provided by Mr.NightZ-1 in artical "193 WA why? What's wrong in my algorithm??????".
However, I got a strange answer diffenent from the one provided by Mr.sohel in some cases...

ex.

inpunt:
20 19
1 10
2 5
3 4
4 9
5 17
6 4
8 19
9 13
10 11
11 14
12 1
13 6
14 3
15 4
16 5
17 8
18 9
19 15
20 4

Mr.sohel's output:
11
1 2 3 6 7 8 9 11 15 16 20

My output:
11
2 4 7 10 12 13 14 16 17 18 19

The total amount of colored nodes is the same, but the node to be colored is quite diefferent @_@

Other cases are also the same. I always got the same amount of colored nodes but with different selections...

I've drew out the real graph and check my answers. They seem to be correct seems the connected component right next to the colored node are kept "clean".

I've noticed that this problem has different possiilities of answer. However, I always got WA even though my answer seems to be correct , comparing with Mr. sohel's, which have got AC.

Can anyone point out the possible mistake I've made?

Thanks. ^^

[shamim]

this problem has a correction program.
That means any valid answer will be accepted.
I guess, your code has slight mistake somewhere.

[LithiumDex]

Whinii: I would be interested in knowing how you cut down on search time with your backtracking method, I got AC using backtracking, however since I could not find an a good method of knowing when the maximum # of black nodes were found, I had used clock() to tell it too stop after 1/2 a second

[LithiumDex]

In my own tests, on my 1ghz, I did the largest dataset I could find on this form in about a second, correctly... I also created my own random dataset, with 100 nodes and 800 edges, which it crunched (although I don't know if correctly), in about 2-3 seconds

But I am unable to get AC.. I need a large number of "evolutionary" steps to get accurate results, but for some reason on the judges PC time is proportional to n^2, although in my code I can see no reason for this... (i.e., I had n/2 steps, and got 1 second WA, changed that to (n/2)+(n/4), and got 2 second WA..

So i'm going to post my code here, hopefully someone can tell me why this is, but I would like to get this AC, just so I can say I solved a contest problem with a genetic algorithm ;P

Code: Select all

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
using namespace std;

#define INIT_POP 400
#define N_MUTATE (((in * 100) / 666)+1)
#define N_STEPS ((in * 3))
//#define MAX_TRYS 10

struct sol
{
    vector<int> N;
    int nblack;
};

vector<sol> pop;
int n;
int in;
vector<int> E[101];
vector<int> eE;

bool isValid ( sol & s )
{
    int i, j;
    
    for (i=0; i<n; i++)
        if (s.N[i] == 2)
        {
            int sz = E[i].size();
            for (j=0; j<sz; j++)
                if (s.N[E[i][j]] == 2)
                    break;

            if (j != sz)
                return false;
        }

    return true;
}

sol mutate ( sol s );

void initPop ( )
{
    pop.clear();

    int i, j;

    for (i=0; i<INIT_POP; i++)
    {
        sol s;

        s.N.clear();
        for (j=0; j<n; j++)
            s.N.push_back(2);
        
        while (!isValid(s))
        {
            int xx = rand()%eE.size();
         
            s.N[eE[xx]] = 1;
        }

        s.nblack = 0;
        for (j=0; j<n; j++)
            if (s.N[j] == 2)
                s.nblack++;

        pop.push_back(s);
    }
}

sol mutate ( sol s )
{
    int nn = N_MUTATE;
    int i;

    sol ret;

    int trys = 0;

    //do
    //{    
        ret = s;

        int blah = rand()%N_MUTATE;
        
        for (i=0; i<blah; i++)
        {
            int cn = rand()%eE.size();
            cn = eE[cn];

            while (ret.N[cn] == 2)
                cn = eE[rand()%eE.size()];

            int j;

            ret.N[cn] = 2;
            ret.nblack++;

            for (j=0; j<E[cn].size(); j++)
            {
                int x = E[cn][j];

                if (ret.N[x] == 2)
                    ret.nblack--;
                ret.N[E[cn][j]] = 1;

            }
        }

        //trys++;

        //if (trys >= MAX_TRYS)
        //    return s;
        
    //} while ( !isValid(ret) );

    return ret;
}

int main ( void )
{
    int cases;

    cin >> cases;
    
    while (cases--)
    {
        int k;
        cin >> n >> k;

        int i, j;

        for (i=0; i<101; i++)
            E[i].clear();
        
        while (k--)
        {
            int frm, too;
            cin >> frm >> too;
            E[frm-1].push_back(too-1);
            E[too-1].push_back(frm-1);
        }

        if (n == 0)
        {
            cout << "0\n";
            continue;
        }
        else if (n == 1)
        {
            cout << "1\n1\n";
            continue;
        }

        eE.clear();
        
        for (i=0; i<n; i++)
            if (E[i].size())
                eE.push_back(i);
        
        in = eE.size();        
        
        srand(0);
        initPop();

        sol final;
        int steps = 0;
        /*int lastmax = 0;
        int beforelast = 0;
        int beforethat = 0;
        int evenbeforethat = 0;*/
        int gmax = 0;

        while (true)
        {
            int mxb = 0, mxi;
            for (i=0; i<pop.size(); i++)
            {
                if (pop[i].nblack > mxb)
                {
                    mxb = pop[i].nblack;
                    mxi = i;
                }
            }

            if (mxb == 0)
                mxi = 0;

            if (mxb > gmax)
            {
                gmax = mxb;
                final = pop[mxi];
            }

            steps++;
            
            if (steps >= N_STEPS)/* ||
               (beforelast > 0 && (lastmax == evenbeforethat) &&
                                  (lastmax == beforethat) &&
                                  (lastmax == beforelast) &&
                                  (lastmax == mxb))*/
               // && gmax == mxb)
            {
                break;
            }

            /*evenbeforethat = beforethat;
            beforethat = beforelast;
            beforelast = lastmax;
            lastmax = mxb;*/

            pop.clear();
            for (i=0; i<INIT_POP; i++)
                pop.push_back(mutate(final));
        }
          
        int last = 0;
        for (i=0; i<n; i++)
            if (final.N[i] == 2)
                last = i;

        cout << final.nblack << endl;

        for (i=0; i<n; i++)
            if (final.N[i] == 2)
            {
                if (i<last)
                    cout << i+1 << " ";
                else
                    cout << i+1 << endl;
            }
    }
}

[Kallol]

I used a Brute Force method . I tried to paint every node BLACK and then tried to find the solution. I did dot get TLE from judge, rather I got WA !!

But my code gave right answers for all the inputs I found. Anyone can help me ??

Code: Select all

#include<stdio.h>
#include<string.h>

#define BLACK 1
#define WHITE 2

bool a[105][105];
int col[105];
int savecol[105];
int blacks,v;

void paint(int index,int c)
{
	int i;
	if(c==BLACK)
	{
		blacks++;
	}
	col[index]=c;
	if(c==BLACK)
	{
		for(i=1;i<=v;i++)
		{
			if(a[index][i])
			{
				paint(i,WHITE);
			}
		}
	}
	return;
}

int main(void)
{

	int t,e,n1,n2,i,j,temp;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&v,&e);

		memset(a,false,sizeof(a));
		memset(col,0,sizeof(col));
		
		for(i=0;i<e;i++)
		{
			scanf("%d%d",&n1,&n2);
			a[n1][n2]=a[n2][n1]=true;
		}

		
		int max=0;
		for(j=1;j<=v;j++)
		{
			memset(col,0,sizeof(col));
			blacks=0;
			paint(j,BLACK);
			for(i=1;i<=v;i++)
			{
				if(col[i]==0)
				{
					paint(i,BLACK);
				}
			}
			if(blacks>max)
			{
				max=blacks;
				for(i=1;i<=v;i++)
				{
					savecol[i]=col[i];
				}
			}
		}
		
		printf("%d\n",max);
		temp=max;
		i=1;
		while(temp>1)
		{
			if(savecol[i]==BLACK)
			{
				printf("%d ",i);
				temp--;
			}
			i++;
		}
		while(savecol[i]==WHITE && i<=v)
		{
			i++;
		}
		printf("%d\n",i);
		
	}
	return 0;
}
[\code]

[smilitude]

i didnt code this problem.
but i think the simplest solution would be..

1. run a bfs
2. bicolor the graph
3. check which color has greater value - black or white
4. if its white, define white as black
5. print nblack, and print the vertex those are black

its not very easy to look through other's code and understand whats going on there!

[mf]

2. bicolor the graph

That's not always possible.

[Kallol]

its not a bi-colorable problem , because two whites can be adjacent. Any way , is there any tricky input to dodge my code ??