Page 6 of 7
uva 10004,why WA? Please help me........
Posted: Thu Jun 27, 2013 4:55 pm
by anup10.duet
Code: Select all
#include<stdio.h>
#include<string.h>
void cycleCheck(int node1);
int visited[250],counter1,numberOfNode,g[250][250],cycle;
int main()
{
int numberOfEdge,index1,index2;
while(scanf("%d",&numberOfNode) == 1)
{
cycle = 0;
if(numberOfNode == 0)
break;
scanf("%d",&numberOfEdge);
memset(g,0,sizeof(g));
memset(visited, 0, sizeof(visited));
for(counter1 = 0;counter1 < numberOfEdge;counter1++)
{
scanf("%d%d",&index1,&index2);
g[index1][index2] = 1;
g[index2][index1] = 1;
}
cycleCheck(0);
if(cycle == 1)
{
printf("NOT BICOLORABLE.\n");
}
else
printf("BICOLORABLE.\n");
}
return 0;
}
void cycleCheck(int node1)
{
visited[node1] += 1;
for(counter1 = 0;counter1 < numberOfNode;counter1++)
{
if(g[node1][counter1] == 1)
{
g[node1][counter1] += 1;
g[counter1][node1] += 1;
if(visited[counter1] == 1)
{
cycle = 1;
break;
}
else
cycleCheck(counter1);
}
}
}
Re: uva 10004,why WA? Please help me........
Posted: Fri Jun 28, 2013 12:03 am
by brianfry713
Re: uva 10004,why WA? Please help me........
Posted: Fri Jun 28, 2013 3:07 pm
by anup10.duet
thank's a lot brianfry713 , I understand my mistake.
Re: uva 10004,why WA? Please help me........
Posted: Mon Jul 01, 2013 11:42 pm
by anup10.duet
got AC!!!!!!!! thanks a lot brianfry713.
Re: 10004 - Bicoloring
Posted: Thu Oct 17, 2013 9:31 pm
by brosa92
I've sent the following code and got WA. Anyone can help me w/ that?
Code: Select all
#include <iostream>
#include <string.h>
using namespace std;
#define _N 205
int adjacencyMatrix[_N][_N];
int color[_N];
int n;
bool dfs(int v, int colorToPaint = 1) {
color[v] = 1;
int nextColor = colorToPaint==1?2:1;
int returnValue;
for (int i = 0; i < n; ++i) {
if (adjacencyMatrix[v][i]) {
if (!color[i]) {
returnValue = dfs(i,nextColor);
} else if (color[i] == colorToPaint) {
return false;
}
if (!returnValue) return false;
}
}
return returnValue;
}
bool isBicolorable() {
return dfs(0);
}
int main() {
int l, u, v;
while (cin >> n) {
if (n == 0) break;
cin >> l;
for (int i = 0; i < n; i++) memset(adjacencyMatrix[i], 0, n*sizeof(int));
memset(color, 0, n*sizeof(int));
for (int i = 0; i < l; ++i) {
cin >> u >> v;
adjacencyMatrix[u][v] = adjacencyMatrix[u][v] = 1;
}
if (isBicolorable()) {
cout << "BICOLORABLE." << endl;
} else {
cout << "NOT BICOLORABLE." << endl;
}
}
return 0;
}
INPUT:
3
3
0 1
1 2
2 0
9
8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
4
4
0 1
1 2
2 3
3 0
5
5
0 1
1 2
2 3
3 4
4 0
3
3
0 1
1 2
2 0
9
8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0
OUTPUT:
NOT BICOLORABLE.
BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
Re: 10004 - Bicoloring
Posted: Fri Oct 18, 2013 7:39 pm
by brianfry713
Try the I/O in this thread.
Re: 10004 - Bicoloring
Posted: Sun Sep 28, 2014 5:20 pm
by musfiqur.cse
I am getting WA .. where is the bug in my code..
Code: Select all
#include<bits/stdc++.h>
using namespace std;
#define PI acos(-1.0)
#define ll long long
#define mem(a) memset(a,0,sizeof(a));
#define M 10000007
int visit[10001],matrix[1000][1000],col[100001],chk;
bool phk;
void dfs(int p)
{
int i,a,b,j;
for(i=0;i<p;i++)
{
visit[i]=1;
if(col[i]==0)
chk=1;
else
chk=0;
for(j=i+1;j<p;j++)
{
if(matrix[i][j]==1)
{
if(col[j]==col[i]&&visit[j]==1)
phk=false;
else
{
visit[j]=1;
col[j]=chk;
}
}
}
if(!phk)
break;
}
}
int main()
{
ios_base::sync_with_stdio(0);
int n,m,k,l,i;
while(cin>>n)
{
if(!n)
break;
phk=true;
cin>>m;
mem(matrix);
mem(visit);
mem(col);
for(i=0;i<m;i++)
{
cin>>k>>l;
matrix[k][l]=1;
matrix[l][k]=1;
}
dfs(n);
if(phk)
cout<<"BICOLORABLE."<<endl;
else
cout<<"NOT BICOLORABLE."<<endl;
}
return 0;
}
Re: 10004 - Bicoloring
Posted: Wed Oct 08, 2014 9:20 am
by Shihab
wa help
Code: Select all
/*------------------------------------------------*/
//Uva Problem No:
//Problem Name :
//Type :
//Author : shihab
//University : DIU
/*------------------------------------------------*/
#include<map>
#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int i,j = 0;
//FILE *fp,*op;
// fp = fopen("Input.txt","r");
//op = fopen("output.txt","w");
int a,n,u,v;
bool graph[202 ][202];
int color[202];
//queue<int>nodes;
while( scanf("%d",&n ),n!=0 )
{
scanf("%d",&a);
for( i = 0; i < 201 ; i++ )
{
color[ i ] = 0;
for( j = 0; j < 201; j++ )
{
graph[i][j] = false;
}
}
i = 1;
while( i <= a )
{
scanf("%d %d",&u,&v);
graph[u][v] = graph[v][u] = true;
i++;
}
int f = 1;
for( i = 0; i < 201 ; i++ )
{
for( j = 0; j < 201; j++ )
{
if( graph[ i ][ j ] == true )
{
if( !color[ i ] )
color[ i ] = -1;
if( !color[ j ] )
color[ j ] = color[ i ] * -1;
if( color[ i ] == color[ j ] )
{
printf("NOT BICOLORABLE.\n");
f = 0;
break;
}
}
}
if( f == 0 )
{
break;
}
}
if( f )
printf("BICOLORABLE.\n");
// nodes.clear();
// nodes.push( 0 );
//
// while( !nodes.empty() )
// {
// int h = nodes.pop();
// color[ h ] = 1;
// for( i = 0;i < n; i++ )
// {
//
// }
//
// }
}
return 0;
}
Re: 10004 - Bicoloring
Posted: Wed Oct 08, 2014 9:48 am
by lighted
Your code fails some random input here.
http://www.udebug.com/UVa/10004
Re: 10004 - Bicoloring
Posted: Wed Oct 08, 2014 10:24 am
by Shihab
4
3
1 2
1 3
2 3
how this is bicolorable? pls explain
Re: 10004 - Bicoloring
Posted: Wed Oct 08, 2014 11:02 am
by lighted
the graph will be strongly connected. That is, there will be at least one path from any node to any other node.
According to problem description inputs below from random input of udebug are invalid.
Code: Select all
4
3
1 2
1 3
2 3
6
4
0 3
1 2
1 4
2 3
0
Try input
Acc Output
Re: 10004 - Bicoloring
Posted: Wed Oct 08, 2014 8:24 pm
by brianfry713
I changed the random input at:
http://www.udebug.com/UVa/10004
to this input:
Code: Select all
10
31
0 1
0 3
0 4
0 5
0 6
0 7
0 8
0 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 3
2 4
2 5
2 8
2 9
3 4
3 9
4 5
4 6
4 7
5 6
5 7
5 8
6 8
6 9
11
29
0 1
0 4
0 9
1 2
1 5
1 8
2 3
2 6
2 7
2 9
2 10
3 4
3 5
3 6
3 7
3 8
3 10
4 7
4 8
4 10
5 6
5 7
5 8
5 9
5 10
6 9
7 9
8 10
9 10
5
7
0 1
0 2
0 3
0 4
1 2
1 3
3 4
9
26
0 1
0 2
0 3
0 4
0 6
1 2
1 3
1 4
1 5
1 7
1 8
2 4
2 5
2 6
2 8
3 4
3 6
3 7
3 8
4 5
4 6
4 7
5 8
6 7
6 8
7 8
15
58
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 9
0 10
0 14
1 2
1 4
1 6
1 8
1 9
1 10
1 11
1 12
1 14
2 3
2 4
2 5
2 8
2 9
2 10
2 12
3 5
3 7
3 8
3 11
3 12
4 8
4 9
4 10
4 13
5 6
5 7
5 11
5 13
6 7
6 9
6 10
6 11
6 12
6 13
6 14
7 8
7 11
7 13
7 14
8 10
8 13
8 14
9 13
10 11
12 13
12 14
13 14
4
5
0 1
0 3
1 2
1 3
2 3
13
57
0 1
0 2
0 3
0 4
0 5
0 7
0 8
0 9
0 10
0 11
1 2
1 3
1 4
1 5
1 6
1 7
1 9
1 11
1 12
2 3
2 8
2 9
2 11
2 12
3 4
3 5
3 9
3 10
3 11
4 7
4 8
4 10
4 11
5 6
5 7
5 8
5 9
5 10
5 11
5 12
6 7
6 8
6 9
6 10
7 9
7 10
7 12
8 9
8 10
8 11
8 12
9 10
9 11
9 12
10 11
10 12
11 12
14
46
0 1
0 2
0 6
0 8
0 9
0 13
1 2
1 3
1 4
1 6
1 8
1 9
1 10
2 3
2 4
2 5
2 8
2 12
3 5
3 7
3 8
3 10
3 11
4 5
4 7
4 9
4 10
4 11
4 13
5 6
5 9
5 12
5 13
6 7
6 9
6 10
6 12
6 13
7 8
7 9
9 10
9 11
9 12
9 13
10 11
10 12
6
11
0 1
0 2
0 3
1 2
1 4
2 3
2 4
2 5
3 4
3 5
4 5
12
33
0 1
0 2
0 4
0 5
0 6
0 7
0 9
0 10
1 3
1 10
2 3
2 5
2 6
2 8
2 9
2 10
2 11
3 4
3 5
3 7
3 11
4 6
4 8
4 10
5 9
5 11
6 7
6 11
7 10
7 11
8 9
9 10
10 11
1
0
6
9
0 1
0 4
0 5
1 2
1 3
1 4
2 3
2 5
3 5
4
3
0 1
1 2
2 3
15
60
0 1
0 2
0 3
0 5
0 6
0 10
0 11
0 13
1 3
1 4
1 8
1 9
1 10
1 11
1 13
1 14
2 3
2 5
2 7
2 9
2 11
3 6
3 8
3 9
3 10
3 11
3 13
3 14
4 7
4 8
4 10
4 12
5 6
5 9
5 10
5 11
5 14
6 9
6 10
6 11
6 12
7 8
7 10
7 11
7 12
7 13
7 14
8 10
8 13
8 14
9 12
9 13
9 14
10 11
10 13
10 14
11 12
11 14
12 13
12 14
18
84
0 1
0 3
0 5
0 7
0 8
0 14
0 15
1 2
1 3
1 4
1 7
1 8
1 9
1 10
1 11
1 13
1 15
2 3
2 5
2 6
2 9
2 11
2 12
2 15
2 16
3 6
3 9
3 13
3 15
3 16
3 17
4 5
4 8
4 9
4 11
4 13
4 15
4 16
4 17
5 6
5 10
5 13
5 15
5 16
6 7
6 10
6 11
6 12
6 13
6 14
6 16
6 17
7 9
7 10
7 12
7 14
7 16
7 17
8 10
8 11
8 13
8 15
8 16
8 17
9 10
9 11
9 12
9 15
9 17
10 14
10 15
10 16
11 12
11 13
11 16
12 13
12 15
13 14
13 15
13 16
14 16
14 17
15 17
16 17
16
71
0 1
0 2
0 6
0 7
0 10
0 12
0 13
0 14
1 2
1 3
1 5
1 9
1 12
1 13
1 15
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
3 4
3 6
3 7
3 10
4 6
4 7
4 8
4 9
4 10
4 11
5 6
5 7
5 8
5 9
5 10
5 12
5 13
5 14
5 15
6 8
6 10
6 13
7 8
7 9
7 10
7 11
7 13
7 14
7 15
8 9
8 10
8 12
8 13
8 14
9 10
9 14
10 11
10 13
10 14
10 15
11 12
11 13
13 14
13 15
1
0
4
5
0 1
0 2
0 3
1 2
1 3
18
87
0 1
0 2
0 5
0 6
0 8
0 13
0 16
0 17
1 2
1 3
1 4
1 6
1 7
1 8
1 9
1 10
1 11
1 13
1 14
1 15
2 3
2 11
2 14
2 16
3 8
3 9
3 10
3 12
3 16
3 17
4 5
4 8
4 11
4 15
5 6
5 7
5 8
5 9
5 10
5 12
5 13
5 14
5 16
5 17
6 7
6 8
6 9
6 10
6 11
6 13
6 14
6 16
6 17
7 10
7 11
7 13
7 17
8 9
8 10
8 13
8 14
8 15
8 16
8 17
9 11
9 13
9 15
9 16
10 12
10 13
10 14
10 15
10 17
11 12
11 15
11 16
12 13
12 14
12 15
12 16
12 17
13 15
13 16
14 17
15 16
15 17
16 17
1
0
4
6
0 1
0 2
0 3
1 2
1 3
2 3
9
25
0 1
0 2
0 4
0 6
0 7
0 8
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 8
3 4
3 5
3 6
3 7
4 7
4 8
5 7
5 8
6 7
6 8
7 8
13
35
0 1
0 2
0 3
0 4
0 5
0 7
0 9
0 12
1 5
1 6
1 7
1 11
2 5
2 6
2 7
2 8
3 5
3 6
3 7
3 10
4 6
4 10
4 12
5 6
5 9
5 10
5 12
6 10
6 11
6 12
7 8
7 10
7 12
9 12
10 11
18
98
0 1
0 3
0 5
0 6
0 7
0 10
0 12
0 14
0 16
1 2
1 3
1 4
1 5
1 6
1 8
1 9
1 11
1 14
1 15
1 17
2 3
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 13
2 14
2 15
3 4
3 5
3 6
3 7
3 8
3 9
3 12
3 13
3 14
3 15
4 5
4 6
4 7
4 11
4 13
4 15
4 17
5 6
5 7
5 8
5 9
5 11
5 13
5 15
5 16
6 7
6 9
6 10
6 13
6 14
6 15
6 16
7 8
7 12
7 13
7 17
8 10
8 12
8 13
8 14
8 15
8 17
9 10
9 12
9 13
9 16
9 17
10 11
10 12
10 14
10 15
10 17
11 12
11 13
11 14
11 15
11 17
12 13
12 15
12 16
12 17
13 15
13 17
14 16
14 17
15 16
16 17
19
100
0 1
0 2
0 3
0 5
0 6
0 7
0 8
0 9
0 11
0 12
0 14
0 15
0 16
0 17
1 2
1 4
1 7
1 9
1 10
1 11
1 14
1 15
1 16
1 17
1 18
2 3
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 14
2 18
3 4
3 6
3 8
3 9
3 10
3 14
3 16
3 18
4 5
4 6
4 10
4 11
4 12
4 14
4 15
4 16
4 17
5 8
5 10
5 12
5 13
5 14
5 15
5 17
5 18
6 8
6 9
6 10
6 13
6 15
7 9
7 10
7 12
7 15
7 16
8 9
8 11
8 12
8 13
8 14
8 15
8 17
8 18
9 11
9 12
9 13
9 16
9 17
10 12
10 13
10 15
10 18
11 12
11 13
11 15
11 16
11 18
12 14
13 16
13 17
14 15
14 16
15 16
16 17
17 18
12
42
0 1
0 2
0 5
0 6
0 7
0 8
0 9
0 11
1 2
1 3
1 4
1 5
1 6
1 9
1 10
1 11
2 3
2 4
2 6
2 9
2 10
2 11
3 9
3 10
3 11
4 8
4 9
5 7
5 8
5 9
5 11
6 7
6 8
6 9
6 11
7 8
7 9
7 10
7 11
8 10
8 11
10 11
18
79
0 1
0 2
0 5
0 6
0 7
0 8
0 12
0 13
0 15
1 2
1 3
1 4
1 11
1 12
1 14
1 16
1 17
2 3
2 4
2 5
2 8
2 9
2 12
2 14
2 17
3 4
3 6
3 9
3 14
3 16
4 5
4 9
4 12
4 14
4 15
4 17
5 7
5 8
5 11
5 12
5 14
6 9
6 10
6 11
6 12
6 16
6 17
7 9
7 11
7 13
7 14
7 15
7 17
8 9
8 10
8 11
8 13
8 14
8 16
9 13
9 14
9 16
9 17
10 12
10 13
10 14
10 15
10 17
11 15
12 13
12 14
12 15
12 17
13 14
13 16
13 17
14 16
14 17
15 17
18
92
0 1
0 2
0 3
0 4
0 6
0 10
0 12
0 13
0 14
0 15
0 16
0 17
1 3
1 4
1 6
1 7
1 8
1 9
1 14
1 15
1 17
2 3
2 4
2 5
2 6
2 8
2 9
2 10
2 13
2 14
2 15
3 4
3 5
3 6
3 7
3 9
3 10
3 11
3 12
3 13
3 14
3 15
3 17
4 5
4 7
4 8
4 9
4 11
4 12
4 13
4 15
4 16
4 17
5 8
5 10
5 13
5 15
6 8
6 9
6 11
6 13
6 14
6 17
7 9
7 12
7 13
7 14
7 15
7 16
8 9
8 10
8 11
8 12
8 13
8 16
9 11
9 12
9 13
9 14
9 15
10 11
10 13
10 14
10 17
11 17
12 14
12 15
12 16
13 14
13 17
14 15
16 17
9
18
0 1
0 3
0 6
0 7
0 8
1 2
1 3
1 4
2 3
2 4
2 7
2 8
3 4
3 5
3 6
4 5
4 8
6 7
11
36
0 1
0 2
0 3
0 4
0 5
0 7
0 9
0 10
1 2
1 3
1 4
1 5
1 7
1 8
1 9
1 10
2 3
2 5
2 7
2 8
2 9
2 10
3 4
3 6
3 8
4 6
4 8
5 7
5 8
6 7
6 8
6 10
7 9
7 10
8 9
8 10
6
13
0 1
0 2
0 3
0 4
0 5
1 2
1 3
1 4
1 5
2 3
2 4
3 4
3 5
3
2
0 1
1 2
1
0
3
3
0 1
0 2
1 2
19
92
0 1
0 2
0 3
0 4
0 5
0 7
0 11
0 13
0 15
0 17
0 18
1 3
1 4
1 5
1 7
1 10
1 11
1 12
1 14
1 16
1 18
2 6
2 8
2 9
2 13
2 15
2 16
3 4
3 6
3 9
3 10
3 11
3 12
3 14
3 15
3 16
3 17
4 5
4 7
4 8
4 11
4 12
4 14
4 15
5 6
5 7
5 8
5 9
5 12
5 13
5 14
5 18
6 7
6 8
6 9
6 12
6 13
6 14
6 15
6 16
6 17
7 8
7 10
7 11
7 12
7 16
7 17
8 9
8 11
8 12
8 13
8 15
8 17
9 10
9 11
9 17
9 18
10 13
11 13
11 16
12 14
12 18
13 15
13 16
13 17
14 15
14 16
14 17
14 18
15 18
16 17
17 18
20
107
0 1
0 2
0 3
0 5
0 6
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0 16
0 17
0 18
0 19
1 2
1 3
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 15
2 5
2 6
2 8
2 9
2 10
2 11
2 12
3 4
3 5
3 6
3 7
3 11
3 14
3 17
4 5
4 6
4 7
4 8
4 11
4 12
4 13
4 14
4 15
4 16
4 17
4 18
4 19
5 6
5 9
5 10
5 18
5 19
6 8
6 12
6 14
6 15
6 19
7 8
7 10
7 11
7 12
7 13
7 14
7 15
7 18
7 19
8 10
8 11
8 12
8 15
8 17
8 18
9 10
9 12
9 13
9 15
9 17
9 18
10 13
10 15
10 18
10 19
11 12
11 14
11 16
11 17
11 18
12 13
12 17
12 19
13 14
13 16
13 17
13 18
14 18
15 16
15 19
16 17
16 19
3
2
0 1
0 2
17
76
0 1
0 2
0 4
0 5
0 12
0 14
1 2
1 4
1 5
1 8
1 11
1 13
1 16
2 3
2 5
2 6
2 7
2 10
2 14
2 16
3 4
3 8
3 10
3 11
3 12
3 13
3 15
3 16
4 5
4 6
4 9
4 11
4 12
4 13
4 14
4 15
4 16
5 6
5 7
5 8
5 9
5 10
5 12
5 15
5 16
6 7
6 9
6 11
6 12
6 13
6 14
7 8
7 10
7 11
7 12
7 14
7 15
7 16
8 9
8 12
8 13
8 15
8 16
9 11
9 13
10 13
10 14
10 16
11 12
11 13
11 14
11 16
12 13
12 14
14 15
14 16
14
49
0 1
0 2
0 3
0 6
0 9
0 11
0 13
1 2
1 3
1 4
1 5
1 9
1 11
1 13
2 8
2 9
2 10
2 11
2 12
3 5
3 6
3 8
3 9
3 12
4 5
4 7
4 8
4 10
4 11
4 12
4 13
5 6
5 8
5 9
5 12
5 13
6 10
6 12
7 11
7 13
8 9
8 10
8 11
8 12
9 11
9 13
10 12
10 13
12 13
3
3
0 1
0 2
1 2
4
4
0 1
0 2
0 3
1 2
17
72
0 1
0 2
0 5
0 6
0 12
0 13
0 14
0 16
1 3
1 4
1 5
1 10
1 11
1 12
1 13
1 14
1 16
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 14
2 16
3 4
3 5
3 6
3 8
3 9
3 11
3 12
3 13
3 14
4 5
4 6
4 13
4 14
4 15
4 16
5 8
5 10
5 12
5 13
5 14
5 15
5 16
6 8
6 9
6 11
6 16
7 15
8 9
8 10
8 14
8 16
9 11
9 12
9 13
9 15
10 16
11 13
11 14
11 16
12 14
12 15
12 16
13 14
13 16
14 15
15 16
20
99
0 1
0 2
0 3
0 8
0 9
0 12
0 13
0 14
0 16
0 17
0 18
0 19
1 2
1 3
1 4
1 5
1 7
1 13
1 14
1 19
2 8
2 9
2 11
2 12
2 13
2 16
3 4
3 5
3 6
3 8
3 9
3 10
3 13
3 14
4 6
4 8
4 11
4 12
4 14
4 16
4 19
5 7
5 8
5 9
5 10
5 13
5 14
5 15
5 17
5 18
6 8
6 9
6 10
6 12
6 13
6 16
6 19
7 8
7 10
7 12
7 16
7 19
8 9
8 10
8 11
8 12
8 13
8 15
8 17
9 11
9 12
9 15
9 16
9 17
9 18
9 19
10 12
10 14
10 15
11 12
11 13
11 15
11 17
11 18
11 19
12 13
12 15
12 18
12 19
13 15
13 17
13 18
13 19
14 15
14 16
14 17
14 18
15 18
17 19
2
1
0 1
8
14
0 1
0 2
0 3
1 3
1 7
2 4
2 5
2 7
3 4
3 7
4 5
4 6
5 7
6 7
7
14
0 1
0 2
0 3
0 4
0 6
1 3
1 4
1 5
2 3
2 4
2 5
3 4
4 5
4 6
12
39
0 1
0 2
0 3
0 5
0 7
0 8
1 2
1 3
1 4
1 5
1 7
1 9
1 10
2 6
2 8
2 9
2 11
3 5
3 7
3 8
3 9
3 11
4 7
4 9
4 10
4 11
5 6
5 7
5 9
5 10
6 7
6 8
6 10
7 10
8 9
8 10
8 11
9 10
10 11
17
79
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 9
0 10
0 14
0 15
0 16
1 3
1 5
1 7
1 8
1 10
1 11
1 15
2 3
2 4
2 6
2 8
2 16
3 4
3 5
3 6
3 7
3 8
3 9
3 11
3 13
3 15
3 16
4 5
4 6
4 7
4 9
4 13
4 14
4 16
5 6
5 9
5 11
5 12
5 14
5 15
6 7
6 8
6 9
6 10
6 12
6 13
6 15
7 8
7 9
7 10
7 11
7 13
7 15
8 10
8 14
8 15
8 16
9 10
9 11
9 13
9 15
10 11
10 13
11 12
11 13
11 14
11 15
12 13
12 15
12 16
13 15
14 16
9
25
0 1
0 3
0 5
0 6
0 7
1 2
1 5
1 6
1 7
1 8
2 5
2 6
2 7
2 8
3 4
3 5
4 5
4 6
4 7
4 8
5 7
5 8
6 7
6 8
7 8
4
6
0 1
0 2
0 3
1 2
1 3
2 3
9
24
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
1 5
1 7
1 8
2 3
2 5
2 6
2 7
3 4
3 6
3 8
4 5
4 6
4 8
6 7
6 8
7 8
18
82
0 1
0 2
0 3
0 4
0 6
0 7
0 8
0 9
0 11
0 13
0 14
0 15
0 16
1 2
1 3
1 7
1 8
1 13
1 15
1 16
1 17
2 3
2 5
2 7
2 8
2 9
2 10
2 13
2 15
3 5
3 9
3 11
3 12
3 13
3 14
3 15
4 6
4 7
4 8
4 10
4 12
4 13
4 16
5 15
6 7
6 9
6 10
6 14
6 15
6 16
6 17
7 8
7 9
7 10
7 13
7 14
7 16
7 17
8 10
8 11
8 13
8 14
8 16
8 17
9 10
9 12
9 15
10 13
10 14
10 15
11 12
11 14
12 13
12 14
12 15
12 17
13 15
14 16
14 17
15 16
15 17
16 17
9
21
0 1
0 2
0 4
0 5
1 2
1 3
1 4
1 7
2 3
2 4
2 6
2 8
3 6
3 7
4 5
5 6
5 7
5 8
6 7
6 8
7 8
20
112
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 12
0 15
0 17
0 18
0 19
1 2
1 4
1 5
1 7
1 8
1 10
1 13
1 14
1 15
1 16
2 3
2 4
2 7
2 8
2 11
2 13
2 19
3 4
3 5
3 6
3 7
3 9
3 10
3 11
3 13
3 14
3 16
3 17
4 5
4 7
4 8
4 9
4 13
4 15
4 16
4 18
4 19
5 6
5 11
5 12
5 14
5 16
5 17
5 18
6 7
6 8
6 10
6 11
6 12
6 13
6 14
6 15
6 17
6 18
6 19
7 9
7 11
7 12
7 14
7 15
7 18
8 9
8 10
8 11
8 12
8 16
8 19
9 10
9 11
9 14
9 15
9 16
9 18
10 12
10 13
10 15
10 16
10 17
10 18
11 12
11 13
11 14
11 15
11 17
11 18
12 14
12 16
13 15
13 16
13 17
13 19
14 15
14 17
14 18
14 19
15 19
16 18
17 18
17
78
0 1
0 2
0 3
0 4
0 5
0 9
0 12
0 14
0 15
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 6
2 7
2 9
2 10
2 11
2 12
2 15
2 16
3 4
3 7
3 8
3 9
3 12
3 13
3 14
3 15
3 16
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 13
4 14
4 15
5 7
5 15
5 16
6 7
6 8
6 11
6 12
6 13
6 15
6 16
7 10
7 11
7 15
7 16
8 9
8 12
8 14
8 15
9 10
9 12
9 13
9 14
9 15
9 16
10 11
10 14
10 15
10 16
12 16
13 14
13 15
13 16
14 16
3
2
0 1
0 2
15
66
0 1
0 2
0 5
0 7
0 8
0 9
0 10
0 12
0 14
1 2
1 4
1 5
1 6
1 9
1 10
1 11
1 13
1 14
2 3
2 4
2 6
2 7
2 9
2 10
2 11
2 12
2 13
2 14
3 6
3 7
3 8
3 9
3 11
4 7
4 8
4 9
4 10
4 11
4 12
4 13
5 6
5 7
5 9
5 13
5 14
6 7
6 8
6 13
6 14
7 8
7 9
7 10
7 11
7 12
7 13
8 9
8 10
9 11
9 12
9 13
10 11
10 12
11 12
11 14
12 13
13 14
5
8
0 1
0 3
0 4
1 2
1 3
2 3
2 4
3 4
3
2
0 1
1 2
18
83
0 1
0 2
0 4
0 7
0 10
0 12
0 14
0 16
0 17
1 2
1 3
1 4
1 5
1 9
1 10
1 11
1 15
1 16
2 3
2 5
2 6
2 7
2 8
2 9
2 10
2 13
2 14
2 15
2 16
2 17
3 4
3 6
3 9
3 11
3 13
3 14
3 16
3 17
4 9
4 10
4 14
4 16
4 17
5 8
5 9
5 11
5 12
5 16
5 17
6 13
6 14
6 16
6 17
7 8
7 9
7 10
7 11
7 13
7 15
8 10
8 11
8 14
8 16
9 10
9 11
9 12
9 13
9 15
9 16
9 17
10 11
10 12
10 17
11 14
11 16
11 17
12 13
13 14
13 15
14 16
14 17
15 16
16 17
8
14
0 1
0 2
0 3
0 4
0 5
0 6
0 7
1 2
2 3
2 6
3 4
3 5
3 6
6 7
9
25
0 1
0 3
0 6
1 2
1 3
1 4
1 6
1 8
2 3
2 4
2 5
2 6
2 7
2 8
3 4
3 6
3 7
4 5
4 6
4 7
5 6
5 7
6 7
6 8
7 8
12
40
0 1
0 2
0 4
0 5
0 6
0 7
0 8
0 9
0 10
1 2
1 3
1 4
1 6
1 7
1 8
1 9
1 11
2 5
2 10
2 11
3 4
3 7
3 9
3 11
4 5
4 6
4 8
4 10
5 6
5 8
5 9
5 10
5 11
6 7
6 10
7 9
7 11
8 11
9 11
10 11
17
67
0 1
0 2
0 4
0 5
0 7
0 9
0 10
0 11
0 13
1 3
1 4
1 7
1 8
1 9
1 10
1 12
1 13
1 16
2 5
2 6
2 7
2 8
2 11
2 12
2 13
2 14
2 16
3 5
3 8
3 11
3 12
3 16
4 5
4 7
4 8
4 10
4 12
4 13
4 15
4 16
5 6
5 7
5 8
5 9
5 10
5 12
5 16
6 8
6 9
6 11
6 15
7 10
7 11
7 12
7 15
8 9
8 11
9 10
9 15
10 15
10 16
11 12
11 13
12 13
12 15
14 15
15 16
8
18
0 1
0 2
0 3
0 4
0 6
1 4
1 6
1 7
2 3
2 4
2 6
3 5
3 7
4 5
4 6
4 7
5 7
6 7
10
31
0 1
0 2
0 3
0 6
0 8
1 2
1 3
1 4
1 9
2 3
2 4
2 6
2 8
2 9
3 5
3 6
3 7
3 8
3 9
4 6
4 8
4 9
5 7
5 8
5 9
6 7
6 8
6 9
7 8
7 9
8 9
13
47
0 1
0 3
0 4
0 7
0 8
0 10
0 11
1 2
1 4
1 5
1 6
1 7
1 8
1 10
1 11
1 12
2 3
2 6
2 7
2 8
2 9
2 12
3 4
3 5
3 7
3 8
3 9
3 10
3 11
4 5
4 6
4 7
4 9
4 10
4 11
5 6
5 8
6 7
6 8
6 9
6 10
6 11
7 9
7 10
7 12
9 11
10 11
20
116
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 14
0 16
0 17
0 19
1 3
1 5
1 6
1 8
1 9
1 10
1 11
1 13
1 14
1 15
1 16
1 18
2 5
2 6
2 7
2 8
2 9
2 12
2 13
2 16
2 17
2 18
2 19
3 4
3 5
3 7
3 8
3 9
3 11
3 12
3 13
3 14
3 15
3 17
3 18
4 5
4 6
4 12
4 13
4 14
4 16
4 18
5 6
5 7
5 8
5 10
5 13
5 14
5 16
5 17
6 8
6 9
6 10
6 11
6 14
6 16
6 17
6 18
6 19
7 8
7 11
7 12
7 15
7 16
7 17
7 19
8 12
8 15
8 16
8 18
9 11
9 14
9 15
10 11
10 13
10 14
10 17
10 18
11 12
11 14
11 16
11 17
11 19
12 15
12 16
12 19
13 14
13 15
13 17
13 19
14 15
14 16
14 17
15 16
15 18
15 19
16 17
16 18
16 19
17 18
17 19
17
87
0 1
0 2
0 3
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 16
1 2
1 5
1 6
1 8
1 9
1 10
1 11
1 12
1 13
1 15
1 16
2 7
2 8
2 10
2 12
2 16
3 4
3 5
3 7
3 12
3 13
3 15
3 16
4 5
4 6
4 8
4 11
4 16
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
5 16
6 8
6 9
6 12
6 13
6 14
6 15
6 16
7 8
7 10
7 11
7 12
7 13
7 14
7 15
8 9
8 11
8 13
8 14
8 15
8 16
9 11
9 12
9 13
10 12
10 14
10 16
11 12
11 14
11 15
11 16
12 14
12 15
12 16
13 14
13 15
14 16
15 16
15
53
0 1
0 2
0 4
0 5
0 6
0 8
0 13
1 2
1 5
1 6
1 9
1 10
1 11
2 3
2 8
2 12
3 4
3 6
3 9
3 10
3 12
3 13
3 14
4 6
4 7
4 8
4 10
4 11
4 13
5 7
5 9
5 12
5 13
5 14
6 8
6 9
6 10
6 11
6 12
6 14
7 9
7 11
7 12
8 11
8 13
9 11
9 14
10 12
10 13
10 14
12 13
12 14
13 14
3
3
0 1
0 2
1 2
8
17
0 1
0 3
0 7
1 2
1 3
1 5
1 6
1 7
2 3
2 7
3 4
3 5
3 6
4 7
5 6
5 7
6 7
7
12
0 1
0 3
0 4
0 5
0 6
1 2
1 4
2 3
2 5
2 6
3 5
3 6
3
2
0 1
1 2
5
6
0 1
0 3
0 4
1 2
1 4
2 4
11
29
0 1
0 2
0 3
0 4
0 6
0 7
0 9
1 2
1 3
1 5
1 7
1 8
2 5
2 8
2 10
3 5
3 9
4 5
4 6
4 9
4 10
5 9
6 7
6 8
6 9
6 10
7 9
8 9
8 10
4
5
0 1
0 2
0 3
1 3
2 3
1
0
8
18
0 1
0 2
0 4
0 5
0 7
1 2
1 3
1 4
1 6
2 3
2 4
2 6
3 4
3 7
4 6
4 7
5 7
6 7
13
47
0 1
0 2
0 5
0 7
0 12
1 3
1 4
1 6
1 8
1 12
2 3
2 4
2 5
2 6
2 7
2 8
2 12
3 4
3 6
3 7
3 8
3 9
3 10
3 11
3 12
4 5
4 6
4 7
4 8
4 11
4 12
5 7
5 8
5 9
5 11
6 7
6 8
6 9
6 10
6 11
7 11
8 11
8 12
9 12
10 11
10 12
11 12
16
57
0 1
0 2
0 3
0 4
0 8
0 12
1 2
1 4
1 7
1 8
1 11
1 12
1 14
2 4
2 9
2 12
2 14
2 15
3 5
3 8
3 11
3 12
3 13
3 14
4 5
4 10
4 12
4 14
4 15
5 6
5 7
5 9
5 10
5 13
5 14
5 15
6 7
6 8
6 9
6 10
6 11
6 13
6 15
7 10
7 11
7 13
7 15
9 10
9 11
9 13
9 15
10 11
10 12
10 14
11 12
11 13
11 15
8
17
0 1
0 2
0 3
0 5
0 7
1 2
1 5
2 3
2 4
2 5
2 6
3 4
3 5
3 6
3 7
4 6
4 7
9
21
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
1 4
1 8
2 3
2 5
2 7
2 8
3 5
3 6
3 8
4 5
4 8
5 7
6 8
4
4
0 1
0 3
1 2
2 3
8
21
0 1
0 2
0 4
0 5
0 6
1 3
1 5
1 6
1 7
2 3
2 4
2 5
2 7
3 4
3 5
3 7
4 5
4 6
4 7
5 6
6 7
13
42
0 1
0 2
0 3
0 4
0 5
0 6
0 10
1 2
1 4
1 5
1 6
1 8
1 9
1 11
2 4
2 5
2 7
2 8
2 9
2 11
3 6
3 9
3 12
4 5
4 6
4 10
4 11
4 12
5 7
5 9
5 10
5 11
6 7
6 8
6 9
6 11
7 11
8 9
8 11
8 12
9 10
11 12
19
88
0 1
0 2
0 3
0 5
0 6
0 8
0 10
0 12
0 15
0 16
0 17
1 6
1 8
1 9
1 16
1 17
1 18
2 4
2 5
2 6
2 7
2 8
2 10
2 11
2 15
3 4
3 6
3 7
3 8
3 10
3 11
3 13
3 15
3 17
4 7
4 9
4 12
4 13
4 15
4 16
5 6
5 10
5 11
5 12
5 13
5 14
5 15
5 16
5 18
6 7
6 8
6 11
6 12
6 13
6 14
6 15
6 17
7 10
7 11
7 13
7 14
7 17
7 18
8 9
8 13
8 14
8 15
9 10
9 12
9 15
9 16
10 11
10 18
11 15
11 16
11 18
12 15
12 16
12 18
13 14
13 15
13 16
13 18
14 15
14 16
14 18
15 17
15 18
9
22
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
1 2
1 4
1 5
1 6
1 7
2 3
2 4
2 5
2 6
2 7
3 7
4 8
6 7
6 8
8
17
0 1
0 2
0 4
1 5
1 6
2 3
2 4
2 5
2 6
2 7
3 5
4 5
4 6
4 7
5 6
5 7
6 7
20
110
0 1
0 2
0 3
0 4
0 5
0 6
0 8
0 10
0 11
0 12
0 14
0 17
1 2
1 3
1 5
1 7
1 8
1 10
1 11
1 13
1 14
1 15
1 18
2 6
2 7
2 9
2 13
2 16
2 17
3 4
3 5
3 6
3 7
3 8
3 14
3 16
3 17
3 18
3 19
4 5
4 7
4 8
4 10
4 12
4 13
4 17
4 19
5 10
5 11
5 12
5 14
5 15
5 17
5 18
5 19
6 8
6 9
6 10
6 13
6 16
6 17
6 18
6 19
7 8
7 9
7 10
7 12
7 13
7 14
7 15
7 16
7 19
8 9
8 10
8 11
8 13
8 14
8 15
8 16
8 19
9 11
9 12
9 13
9 17
9 19
10 13
10 15
10 16
10 17
10 18
11 14
11 15
11 16
11 17
12 16
12 17
12 18
12 19
13 15
13 16
13 19
14 15
14 18
15 16
15 18
15 19
16 18
16 19
17 19
18 19
16
64
0 1
0 2
0 3
0 4
0 5
0 10
0 11
0 12
0 13
0 14
1 2
1 6
1 8
1 10
1 13
1 15
2 4
2 5
2 9
2 12
3 4
3 5
3 7
3 12
3 14
3 15
4 5
4 6
4 7
4 9
4 10
5 7
5 8
5 9
5 10
5 11
5 12
5 13
5 14
6 7
6 9
6 10
6 11
6 13
6 15
7 8
7 9
7 12
7 13
8 9
8 11
8 12
8 13
8 15
9 11
9 13
9 14
9 15
10 11
10 13
10 14
11 13
11 14
12 14
2
1
0 1
5
9
0 1
0 2
0 4
1 2
1 3
1 4
2 3
2 4
3 4
4
5
0 1
0 3
1 2
1 3
2 3
7
14
0 1
0 2
0 3
0 4
0 6
1 2
1 3
1 5
1 6
2 3
3 4
3 5
3 6
4 6
18
81
0 1
0 2
0 3
0 4
0 6
0 9
0 10
0 11
0 12
0 13
0 16
1 2
1 3
1 5
1 8
1 9
1 10
1 11
1 15
1 17
2 5
2 7
2 8
2 9
2 12
2 13
2 15
2 16
3 4
3 5
3 6
3 7
3 9
3 10
3 11
3 13
3 14
3 15
3 16
4 5
4 8
4 9
4 16
5 8
5 11
5 12
5 13
5 16
5 17
6 7
6 9
6 11
6 12
6 13
6 14
6 16
7 9
7 12
7 14
7 15
8 10
8 12
8 16
9 10
9 17
10 11
10 16
11 12
11 13
11 14
11 15
11 17
12 14
12 16
12 17
13 14
13 15
13 16
13 17
14 15
15 17
11
35
0 1
0 2
0 3
0 5
0 8
1 2
1 3
1 5
1 7
1 8
1 9
1 10
2 3
2 4
2 5
2 7
2 8
2 9
3 4
3 7
3 8
3 10
4 5
4 6
4 7
4 8
5 6
5 7
5 8
5 9
5 10
6 9
6 10
8 9
8 10
13
43
0 1
0 2
0 3
0 4
0 7
0 9
1 3
1 5
1 7
1 8
1 10
2 3
2 4
2 5
2 6
2 9
2 11
2 12
3 5
4 7
4 10
4 11
5 6
5 10
5 12
6 7
6 8
6 9
6 11
7 8
7 9
7 10
7 11
7 12
8 9
8 10
8 11
8 12
9 10
9 11
9 12
10 11
10 12
13
39
0 1
0 2
0 3
0 4
0 5
0 9
0 10
0 12
1 2
1 3
1 5
1 6
1 8
1 9
2 6
2 7
2 8
2 10
3 5
3 6
3 8
3 9
3 10
3 12
4 6
4 7
4 8
4 9
4 11
5 6
5 11
6 7
6 10
7 8
7 10
8 11
8 12
9 10
10 12
15
54
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 9
0 11
0 13
0 14
1 7
1 10
1 11
1 12
2 3
2 4
2 6
2 7
2 12
3 4
3 9
3 13
4 5
4 6
4 7
4 9
4 10
4 11
4 12
5 6
5 8
5 11
5 13
6 7
6 8
6 10
6 11
6 13
7 10
7 11
7 12
8 10
8 11
8 12
9 10
9 11
9 14
10 11
10 12
11 12
11 13
11 14
13 14
0
AC output:
Code: Select all
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
NOT BICOLORABLE.
Re: 10004 - Bicoloring
Posted: Wed Oct 08, 2014 8:38 pm
by brianfry713
musfiqur.cse and Shihab, try input:
AC output: BICOLORABLE.
Try using a DFS that visits the nodes in the correct search order, use recursion or a stack.
http://en.wikipedia.org/wiki/Depth-first_search
Re: 10004 - Bicoloring
Posted: Mon Nov 03, 2014 1:00 pm
by efrshuvo
It is really too much frustrating. All sample input output passed ( All posted in this thread) but still WA.
Code: Select all
#include<cstdio>
#include<list>
#include<cstring>
#define MAX_NODE 200
#define MAX_EDGE 10000
using namespace std;
int colored[MAX_NODE];
int dfs(list<int> adj[],int v,int visited[],int color=1,int parent=0)
{
visited[v]=1;
colored[v]=!color;
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
{
if(!visited[*i])
return dfs(adj,*i, visited,!color,v);
else
if(*i!=parent)
{
if(colored[v]==colored[*i])
return 0;
}
}
return 1;
}
int is_bicolorable(list<int> adj[],int v,int visited[],int n)
{
for(int i = 0; i < n; i++)
{
if(!visited[i])
{
if(!dfs(adj, i,visited))
return 0;
}
}
return 1;
}
int main()
{
int n,u,v;
long l;
list<int> adj[MAX_EDGE];
int visited[MAX_NODE];
short bicolored=1;
//freopen("E:\\acm\\10004_in.txt","r",stdin);
while(1)
{
memset(visited, 0,sizeof(visited));
memset(colored, -1,sizeof(colored));
scanf("%d",&n);
if(n<=0)
break;
scanf("%ld",&l);
for(long i=0;i<l;i++)
{
scanf("%d %d",&u,&v);
adj[u].push_back(v);
adj[v].push_back(u);
}
bicolored=is_bicolorable(adj,0,visited,n);
if(!bicolored)
printf("NOT BICOLORABLE.\n");
else
printf("BICOLORABLE.\n");
for(long i=0;i<l;i++)
{
adj[i].clear();
}
}
return 0;
}
Thanks.
Re: 10004 - Bicoloring
Posted: Mon Nov 03, 2014 2:18 pm
by lighted
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.
