Page 4 of 7
help with problem 193
Posted: Sun Jun 19, 2005 4:43 pm
by 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
and get's output:
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.
Posted: Sun Jun 19, 2005 6:05 pm
by 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.
Posted: Mon Jun 20, 2005 4:20 pm
by 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;
}
Posted: Mon Jun 20, 2005 6:48 pm
by 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.
Posted: Mon Jun 20, 2005 6:51 pm
by 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.
HOW CAN I SOLVE PROBLEM 193
Posted: Wed Nov 30, 2005 12:27 pm
by MD. OMAR FARUQUE
IT IS A GRAPH PROBLEM.
I AM WEAK IN GRAPH . HOW I CAN I SOLVE IT. HAVE ANYBODY TO HELP ME.
193...WA??
Posted: Mon Jul 31, 2006 7:04 pm
by 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
193 - Graph Coloring
Posted: Tue Aug 08, 2006 10:49 pm
by 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. ^^
Posted: Wed Aug 09, 2006 8:57 am
by shamim
this problem has a correction program.
That means any valid answer will be accepted.
I guess, your code has slight mistake somewhere.
Posted: Mon Aug 28, 2006 10:35 pm
by 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
193... My attempt with a Genetic Algorithm
Posted: Tue Aug 29, 2006 2:45 am
by 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;
}
}
}
Posted: Sun Jul 08, 2007 2:58 pm
by 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]
Posted: Mon Jul 09, 2007 1:51 am
by 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!
Posted: Mon Jul 09, 2007 2:29 am
by mf
smilitude wrote:2. bicolor the graph
That's not always possible.
Posted: Mon Jul 09, 2007 9:48 pm
by Kallol
its not a bi-colorable problem , because two whites can be adjacent. Any way , is there any tricky input to dodge my code ??
