UVA 10004

UVA 10004 ：https://uva.onlinejudge.org/external/100/10004.pdf









/*DFS , bipartite graph*/










#include<iostream>
#include<cstring>
using namespace std;
#define size 205
int matrix[size][size];
int color[size];
int n = 0;

int dfs(int start) {

for (int end= 0; end < n; end++)
{
//matirx[start][end] = 1 , means start vertex and end vertex was connected
if (matrix[start][end])
{
//if end vertex hasn't be check, then drew color and keep going next adjacent vertex
if (!color[end]) {
color[end] = !color[start];
dfs(end);
}

// based on end vertex has been check before
// start vertex and end vertex color have the same color, means color already repeat ,so cant be drew correct
else if (color[start] == color[end])
return 0;
}
}
return 1;
}

int main(void) {

while (1)
{
int l = 0,row=0,col=0;
cin >> n;

if (n == 0)break;
cin >> l;

memset(matrix, 0, sizeof(matrix));
memset(color, 0, sizeof(color));
    /*
1: connected and colored
0: disconncted and uncolored
*/
for (int i = 0; i < l; i++)
{
cin >> row >> col;
matrix[row][col] = matrix[col][row] = 1;
}
color[0] = 1;
if (dfs(0))
cout<<"BICOLORABLE." <<endl;
else
cout << "NOT BICOLORABLE."<< endl;

}

}