10004 - Bicoloring

[efrshuvo]

Problem description says

the graph will be strongly connected. That is, there will be at least one path from any node to any other node.

So your function is_bicolorable is unnecessary.

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);

Wow. great. thanks for your help. but still can't understand why my previous code was not accepted ?

[brianfry713]

The judge's I/O is correct.

Change line 79 to:
for(long i=0;i<n;i++)

[ashdboss]

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

[brianfry713]

Change line 172 to:
for(i=0;i<NODES;i++)