OJ Board

Code: Select all

4
3
0 3
1 2
2 3
0

Code: Select all

spelling mistake. lol

Code: Select all

 GoT AC --
Dont Forget The dot at the end of your Lines 

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

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

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

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

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