Desafios: Bicoloring

main.cpp

#include <iostream>

using namespace std;

int matrix[199][199]; //maximo eh 200
int gr[199];
int x[199];
bool isBicolorable;

void f(int n){
    for(int i=0;i<gr[n]&&isBicolorable;i++){
        if(x[matrix[n][i]]==-1){
            x[matrix[n][i]]=1-x[n];
            f(matrix[n][i]);
        }else if(x[n]==x[matrix[n][i]]){
			isBicolorable=false;
	}
    }
}

int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);

    int n,l,a,b;
    
    while(true){
        cin>>n;
        if(n==0) break;
        cin>>l;
        for(int i=0;i<n;i++) gr[i]=0;
        for(int i=0;i<l;i++){
            cin>>a>>b;
            matrix[a][gr[a]]=b;
            gr[a]++;
            matrix[b][gr[b]]=a;
            gr[b]++;
        }
        isBicolorable=true;
        for(int i=0;i<n;i++) x[i]=-1;        
        for(int i=0;i<n && isBicolorable;i++){
            if(x[i]==-1){
                x[i]=0;
                f(i);
            }
        }
        if(isBicolorable) cout<<"BICOLORABLE."<<endl;
        else cout<<"NOT BICOLORABLE."<<endl;
    }

    return 0;
}