Wow. great. thanks for your help. but still can't understand why my previous code was not accepted ?lighted wrote:Problem description saysSo your function is_bicolorable is unnecessary.the graph will be strongly connected. That is, there will be at least one path from any node to any other node.
I don't know why you got WA. Maybe judge's input contains invalid input. But if you change line this way you'll get Acc.![]()
Code: Select all
bicolored = dfs(adj, 0, visited);
10004 - Bicoloring
Moderator: Board moderators
Re: 10004 - Bicoloring
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10004 - Bicoloring
The judge's I/O is correct.
Change line 79 to:
for(long i=0;i<n;i++)
Change line 79 to:
for(long i=0;i<n;i++)
Check input and AC output for thousands of problems on uDebug!
Re: 10004 - Bicoloring
getting wrong answer.need help
Code: Select all
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdio>
#include<stdlib.h>
#include <queue>
#include<string>
#include<cstring>
#include<sstream>
#include<list>
#include<math.h>
#include<map>
#include<set>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<fstream>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define PB push_back
#define PI acos(-1.0)
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define READ freopen("input.txt", "r", stdin)
#define WRITE freopen("output.txt", "w", stdout)
#define LL long long
#define MOD 1000000007
#define MX 100010
#define pii pair<int,int>
#define mx 20005
#define INF 99999999
int NODES,EDGES;
int fx[]={1,-1,0,0,1,1,-1,-1};
int fy[]={0,0,1,-1,1,-1,1,-1};
char cell[105][105];
int d[105][105],vis[105][105];
int row,col;
#define MOD 1000000007
#define MX 100010
vector<int>visit;
int color[300];
vector<int>adj[300];
struct two
{
int a,b;
bool operator<(const two& t)const
{
if(b==t.b)
return a<t.a;
return (a<t.a)&&(b<t.b);
}
};
int check(int tx,int ty)
{
if(tx>=0 && tx<row && ty>=0 && ty<col)
return 1;
return 0;
}
struct graph{
int x;
int y;
};
struct prior_to{
prior_to(){
main_element ="";
no_of_prior_element_left =0;
}
vector<string> parent;
string main_element;
int no_of_prior_element_left;
};
string rotate(vector<int>X,int index)
{
string str ="";
char ch;
int k,y,x,m,n=X.size();
for(k= index,y=0;y<n;k++,y++)
{
m = k%n;
x = X[m];
ch = x+'0';
str = str+ch;
}
return str;
}
#define RED 1
#define WHITE 0
bool BFS(int src)
{
queue<int>Q;
//int parent[100],level[100];
Q.push(src);
visit[src] = 1;
if(color[src]==-1)
color[src] = RED;
while(!Q.empty())
{
int u = Q.front();
for(int i = 0 ;i<adj[u].size();i++)
{
int v = adj[u][i];
int c = color[u];
if(color[v]!=c )
color[v] = (c+1)%2;
else
return false;
if(!visit[v])
{
visit[v] = 1;
Q.push(v);
}
}
Q.pop();
}
return true;
}
int main()
{
int n,m,x,y,i,j,sum,flag;
int no_of_prior[102],no_dependency,index_of_dependent,k,smallest_index;
char ch;
string str;
set<int>X;
vector<int>Y;
int test_case=0,min= 999999999,first,last,a,b;
//freopen ("d:/codejam_input/A-large-practice.out","w",stdout);
int answer[200005];
while(scanf ("%d" ,&a)==1)
{
if(a==0)
break;
scanf("%d",&b);
NODES = a;
EDGES =b;
flag = 0;
for(i=0;i<=NODES;i++)
{
color[i]=-1;
visit.push_back(0);
}
for(i=0;i<EDGES;i++)
{
scanf("%d%d",&n,&m);
adj[n].push_back(m);
adj[m].push_back(n);
}
for(i=0;i<NODES;i++)
{
for(j=0;j<NODES;j++)
visit.push_back(0);
if(!visit[i])
{
if(!BFS(i))
{
flag =1;
break;
}
}
}
visit.clear();
for(i=0;i<EDGES;i++)
adj[i].clear();
if(flag)
printf("NOT BICOLORABLE.\n");
else
printf("BICOLORABLE.\n");
}
return 0;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10004 - Bicoloring
Change line 172 to:
for(i=0;i<NODES;i++)
for(i=0;i<NODES;i++)
Check input and AC output for thousands of problems on uDebug!