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

geran
New poster
Posts: 13
Joined: Sun Jun 19, 2005 4:36 pm

help with problem 193

Post by geran » Sun Jun 19, 2005 4:43 pm

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 :lol:) on my small graphs. Can somebody please give me a larger graph and the output of you AC solution.

geran
New poster
Posts: 13
Joined: Sun Jun 19, 2005 4:36 pm

Post by geran » Sun Jun 19, 2005 6:05 pm

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
New poster
Posts: 13
Joined: Sun Jun 19, 2005 4:36 pm

Post by geran » Mon Jun 20, 2005 4:20 pm

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Jun 20, 2005 6:48 pm

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
New poster
Posts: 13
Joined: Sun Jun 19, 2005 4:36 pm

Post by geran » Mon Jun 20, 2005 6:51 pm

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
New poster
Posts: 2
Joined: Tue May 31, 2005 7:55 am
Location: CHITTAGONG

HOW CAN I SOLVE PROBLEM 193

Post by MD. OMAR FARUQUE » Wed Nov 30, 2005 12:27 pm

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

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

193...WA??

Post by asif_rahman0 » Mon Jul 31, 2006 7:04 pm

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
New poster
Posts: 4
Joined: Tue Aug 08, 2006 10:36 pm

193 - Graph Coloring

Post by anne0604 » Tue Aug 08, 2006 10:49 pm

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

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Wed Aug 09, 2006 8:57 am

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

LithiumDex
New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm
Location: Nova Scotia, Canada
Contact:

Post by LithiumDex » Mon Aug 28, 2006 10:35 pm

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 :P
- Chris Adams

LithiumDex
New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm
Location: Nova Scotia, Canada
Contact:

193... My attempt with a Genetic Algorithm

Post by LithiumDex » Tue Aug 29, 2006 2:45 am

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;
            }
    }
}
- Chris Adams

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Sun Jul 08, 2007 2:58 pm

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]
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Mon Jul 09, 2007 1:51 am

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! :(
fahim
#include <smile.h>

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Jul 09, 2007 2:29 am

smilitude wrote:2. bicolor the graph
That's not always possible.

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Mon Jul 09, 2007 9:48 pm

its not a bi-colorable problem , because two whites can be adjacent. Any way , is there any tricky input to dodge my code ??
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

Post Reply

Return to “Volume 1 (100-199)”