10004 - Bicoloring

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

[brianfry713]

Input:

Code: Select all

4
4
0 1
1 2
2 3
3 0
0

AC output:

Code: Select all

BICOLORABLE.

[anup10.duet]

thank's a lot brianfry713 , I understand my mistake.

[anup10.duet]

got AC!!!!!!!! thanks a lot brianfry713.

[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.

[brianfry713]

Try the I/O in this thread.

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

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

[lighted]

Your code fails some random input here. http://www.udebug.com/UVa/10004

[Shihab]

4
3
1 2
1 3
2 3
how this is bicolorable? pls explain

[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

Code: Select all

5
4
0 3
1 2
1 4
2 3
0

Acc Output

Code: Select all

BICOLORABLE.

[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.

[brianfry713]

musfiqur.cse and Shihab, try input:

Code: Select all

4
3
0 3
1 2
2 3
0

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

[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.

[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.

Code: Select all

bicolored = dfs(adj, 0, visited);