10004 - Bicoloring
Moderator: Board moderators
I can't understand your program well. Could you give a brief explanation of you algorithm ?
Then it well be much more easier to understand and debug.
EDIT : When you post your code, use Code tags.
EDIT : OK. I understood your algorithm. Actually its not correct. I'll make a critical test case.
----
Rio
Then it well be much more easier to understand and debug.
EDIT : When you post your code, use Code tags.
EDIT : OK. I understood your algorithm. Actually its not correct. I'll make a critical test case.
----
Rio
-
- New poster
- Posts: 38
- Joined: Tue Jul 17, 2007 3:21 pm
- Location: East West University
-
- Experienced poster
- Posts: 162
- Joined: Thu Jul 13, 2006 7:07 am
- Location: Campus Area. Dhaka.Bangladesh
- Contact:
Re: 10004 - Bicoloring WA
Fuad Hassan EW
what was your algorithm?
you can place your code.
what was your algorithm?
you can place your code.
Re: 10004 - Bicoloring
At lastttttttttt GOT ACCEPTED yeyeye:
My Algo:Using like floyd Warshall starting from any first vertex(let A)...color it 1...take all of its adjacent(let B,C) ..(Now i will color all adjacent of A to -1 but i will have to check a condition that after coloring any adjacent of -1 color should not have -1 color)...for that now taking first adjacent(B) check all adjacent of that adjacent(B)..let(D,E) if anyone of D or E has the same color(-1) ..then it means graph is not bicolorable else if all conditions gaot satisfied for all vertex IT is biclorable...
My Algo:Using like floyd Warshall starting from any first vertex(let A)...color it 1...take all of its adjacent(let B,C) ..(Now i will color all adjacent of A to -1 but i will have to check a condition that after coloring any adjacent of -1 color should not have -1 color)...for that now taking first adjacent(B) check all adjacent of that adjacent(B)..let(D,E) if anyone of D or E has the same color(-1) ..then it means graph is not bicolorable else if all conditions gaot satisfied for all vertex IT is biclorable...
"Accepted" is my passion but RTE is my weakness.....
-
- New poster
- Posts: 3
- Joined: Sat May 16, 2009 3:40 am
Re: 10004 - Bicoloring
Below is my code. What is the problem
![:(](./images/smilies/icon_frown.gif)
Code: Select all
spelling mistake. lol
Re: 10004 - Bicoloring
Can Sombody help me with my WA!!
Code: Select all
GoT AC --
Dont Forget The dot at the end of your Lines
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)
Beliefs are not facts, believe what you need to believe;)
-
- New poster
- Posts: 25
- Joined: Fri Apr 17, 2009 8:24 am
Re: 10004 - Bicoloring
I am getting WA in this problem....please help
Code: Select all
#include<stdio.h>
#include<queue>
#define MAX 201
using namespace std;
queue<int>ans;
int n,e;
int path[MAX][MAX];
int col[MAX];
void ini(){
for(int i=0;i<MAX;i++){
for(int j=0;j<MAX;j++)
path[i][j]=0;
col[i]=0;
}
}
int bfs(int u){
int temp;
ans.push(u);
col[u]=1;
while(!ans.empty()){
temp=ans.front();
ans.pop();
for(int i=0;i<n;i++){
if(path[temp][i]==1){
if(col[i]==0){
ans.push(i);
if(col[temp]==1)
col[i]=2;
else
col[i]=1;
}
else if(col[i]==col[temp])
return 0;
}
}
}
return 1;
}
int main(){
freopen("1004.txt","r",stdin);
int a,b,val;
while((scanf("%d",&n)==1)){
if(n==0)
break;
scanf("%d",&e);
ini();
for(int i=0;i<e;i++){
scanf("%d %d",&a,&b);
path[a][b]=path[b][a]=1;
}
if(e>0)
val=bfs(a);
else
val=1;
if(val==0)
printf("NOT BICOLORABLE.\n");
else
printf("BICOLORABLE.\n");
}
return 0;
}
-
- Learning poster
- Posts: 64
- Joined: Fri Sep 25, 2009 11:29 am
- Location: Chittagong,University of chittagong
- Contact:
Re: 10004 - Bicoloring
" freopen("1004.txt","r",stdin);
int a,b,val;
while((scanf("%d",&n)==1)){
if(n==0)
"
your program reads input from a file
how can it possible
just comment the line like
// freopen("1004.txt","r",stdin)
int a,b,val;
while((scanf("%d",&n)==1)){
if(n==0)
"
your program reads input from a file
how can it possible
just comment the line like
// freopen("1004.txt","r",stdin)
Try to catch fish rather than asking for some fishes.
Re: 10004 - Bicoloring
Just got AC on this problem. Some tips:
1. Don't assume that there will be node 0, so don't start your BFS at node 0, use other trick![:)](./images/smilies/icon_smile.gif)
2.
1. Don't assume that there will be node 0, so don't start your BFS at node 0, use other trick
![:)](./images/smilies/icon_smile.gif)
2.
Code: Select all
Color the starting node ( passed to your BFS func ) with color 1 and enqueue it
for each adjacent node
if not visited already
mark visited
color it with the opposite of the parent color
enqueue it
else
if parentColor == currentNodeColor
"NOT BICOLORABLE."
"BICOLORABLE."
-
- New poster
- Posts: 5
- Joined: Wed Aug 11, 2010 8:52 am
Re: 10004 - Bicoloring
I am asraful .
I tried to solve 10004
But i am getting WA .
Please help !
Here is my code ...
I tried to solve 10004
But i am getting WA .
Please help !
Here is my code ...
Code: Select all
#include<stdio.h>
int main(){
int m[203][203],a[203],d[203],p[5],l,e,n,i,j,k;
char c[203];
while(scanf("%d",&n) && n){
for(i=0;i<203;++i)
for(j=0;j<203;++j)
m[i][j]=0;
for(i=0;i<203;++i)
{
a[i]=i;
c[i]='Z';
d[i]=0;
}
for(i=0;i<5;i++)
p[i]=0;
scanf("%d",&e);
for(i=1;i<=e;++i){
scanf("%d%d",&j,&k);
m[j][k]=m[k][j]=1;
}
for(i=0;i<n;++i){
k=0;
for(j=0;j<n;++j)
if(m[i][j]==1)
++k;
d[i]=k;
}
for(i=0;i<n-1;++i)
for(j=i+1;j<n;++j)
if(d[i]<d[j]){
k=d[i];
d[i]=d[j];
d[j]=k;
k=a[i];
a[i]=a[j];
a[j]=k;
}
// /* Coloring *///
l=0;
c[a[0]]='A';
for(i=0;i<n;++i){
if(c[a[i]]=='Z'){
for(j=0;j<n;++j)
if(m[a[i]][j]==1){
if(c[j]!='Z'){
p[c[j]-'A']=1;
}
}
j=0;
for(k=0;k<4;k++){
if(p[k]==0&&j==0){
if(k==0)
c[a[i]]='A';
else if(k==1)
c[a[i]]='B';
else if(k==2)
c[a[i]]='C';
else
c[a[i]]='D';
j=1;
}
p[k]=0;
}
}
for(l=0;l<n;++l)
if(m[a[i]][l]==1){
if(c[l]=='Z'){
for(j=0;j<n;++j)
if(m[l][j]==1){
if(c[j]!='Z'){
p[c[j]-'A']=1;
}
}
j=0;
for(k=0;k<4;k++){
if(p[k]==0&&j==0){
if(k==0)
c[l]='A';
else if(k==1)
c[l]='B';
else if(k==2)
c[l]='C';
else
c[l]='D';
j=1;
}
p[k]=0;
}
}
}
}
// Bicoloring ? //
l=0;
for(i=0;i<n;++i)
if(c[i]=='C' || c[i]=='D')
{ l=1; break; }
if(l==0)
printf("BICOLORABLE.\n");
else
printf("NOT BICOLORABLE.\n");
}
return 0;
}
Re: 10004 - Bicoloring WA
my problem gives me correct output for all possible input given in different threads, but it is WA. what is the problem can anyone tell me please...
here is the code
here is the code
Code: Select all
#include<iostream>
#include<cstdio>
#include<queue>
#define MAX 201
using namespace std;
queue<int>que;
int n,m;
int path[MAX][MAX];
int color[MAX];
void initialize(){
int i,j;
for(i=0; i<MAX; i++){
for(j=0; j<MAX; j++){
path[i][j] = 0;
}
color[i] = 0;
}
}
int bfs(int u){
int temp;
int i;
que.push(u);
color[u] = 1;
while(!que.empty()){
temp = que.front();
que.pop();
for(i=0; i<n; i++){
if(path[temp][i]==1){
if(color[i]==0){
que.push(i);
if(color[temp] == 1)
color[i] = 2;
else color[i] = 1;
}
else if(color[i] == color[temp])
return 0;
}
}
}
return 1;
}
int main(){
int a,b,i,value;
//freopen("10004.txt","r",stdin);
while(scanf("%d",&n)==1&&n){
scanf("%d",&m);
initialize();
for(i=0; i<m; i++){
scanf("%d %d",&a,&b);
path[a][b] = path[b][a] = 1;
}
if(m>0)
value = bfs(a);
else
value = 1;
if(value==0)printf("NOT BICOLORABLE.\n");
else printf("BICOLORABLE.\n");
}
return 0;
}
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/
http://akanoi.webs.com/
-
- New poster
- Posts: 1
- Joined: Tue Jul 26, 2011 1:08 am
Re: 10004 - Bicoloring - Runtime Error
My solution is getting Runtime Error in 0.000s, but it works for all instances I've found in this board.
I don't know what is wrong. Is there a special test case that my code is not ready for?
Here is my code:
Thanks in advance.
I don't know what is wrong. Is there a special test case that my code is not ready for?
Here is my code:
Code: Select all
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define MAX_V 205
#define RED 0
#define BLACK 1
#define EMPTY -1
vector<int> colors(MAX_V, EMPTY);
vector<int> grafo[MAX_V]; /* lista de adjacencias */
void reset()
{
for (int i = 0; i < MAX_V; i++)
{
colors[i] = EMPTY;
grafo[i].clear();
}
}
int coloring(int v, int cor)
{
int anticor = 1-cor;
colors[v] = anticor;
vector<int>::iterator it;
for (it = grafo[v].begin(); it != grafo[v].end(); it++)
{
if (colors[*it] == EMPTY)
{
if (coloring(grafo[v][*it], anticor) == 0)
return 0;
}
else if (colors[*it] == anticor) return 0;
}
return 1;
}
int main(int argc, char** argv)
{
int n_vertices, n_arestas; /* number of vertices and arestas */
int x, y;
int is_bicolor;
while (1)
{
cin >> n_vertices;
if (n_vertices == 0) break;
cin >> n_arestas;
reset();
while (n_arestas--)
{
cin >> x >> y;
grafo[x].push_back(y);
grafo[y].push_back(x);
}
/* verifica se eh bicolor */
colors[0] = BLACK;
for (int i = 0; i < grafo[0].size(); i++)
if (colors[i] == EMPTY)
is_bicolor = coloring(i, BLACK);
if (is_bicolor)
cout << "BICOLORABLE." << endl;
else
cout << "NOT BICOLORABLE." << endl;
}
return 0;
}