UVa 10004 - Bicoloring
// Accepted
#include<bits/stdc++.h>
using namespace std;
const int high = 500;
vector<int>adj[high];
int color[high];
bool bicolorable = true;
void adj_clear()
{
for(int i=0; i<high; i++) adj[i].clear();
}
void BFS(int s)
{
queue<int>Q;
color[s] = 0;
Q.push(s);
while(!Q.empty())
{
int u = Q.front();
Q.pop();
for(int i=0; i<adj[u].size(); i++)
{
int v = adj[u][i];
if(!color[v])
{
Q.push(v);
color[v] = 1 + color[u]; // Just increase one from its parent node to make difference between two nodes.
}
else if(color[u] == color[v])
{
bicolorable = false;
break;
}
}
if(!bicolorable) break;
}
}
int main()
{
//freopen("in.txt" , "r" , stdin);
ios_base::sync_with_stdio(false);
int i , n , l , u , v;
while(cin >> n >> l)
{
if(!n) break;
bicolorable=true;
memset(color , 0 , sizeof color);
adj_clear();
for(i=0; i<l; i++)
{
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(i=0; i<n; i++)
{
BFS(i);
if(!bicolorable) break;
}
if(bicolorable) cout << "BICOLORABLE.\n";
else cout << "NOT BICOLORABLE.\n";
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int high = 500;
vector<int>adj[high];
int color[high];
bool bicolorable = true;
void adj_clear()
{
for(int i=0; i<high; i++) adj[i].clear();
}
void BFS(int s)
{
queue<int>Q;
color[s] = 0;
Q.push(s);
while(!Q.empty())
{
int u = Q.front();
Q.pop();
for(int i=0; i<adj[u].size(); i++)
{
int v = adj[u][i];
if(!color[v])
{
Q.push(v);
color[v] = 1 + color[u]; // Just increase one from its parent node to make difference between two nodes.
}
else if(color[u] == color[v])
{
bicolorable = false;
break;
}
}
if(!bicolorable) break;
}
}
int main()
{
//freopen("in.txt" , "r" , stdin);
ios_base::sync_with_stdio(false);
int i , n , l , u , v;
while(cin >> n >> l)
{
if(!n) break;
bicolorable=true;
memset(color , 0 , sizeof color);
adj_clear();
for(i=0; i<l; i++)
{
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(i=0; i<n; i++)
{
BFS(i);
if(!bicolorable) break;
}
if(bicolorable) cout << "BICOLORABLE.\n";
else cout << "NOT BICOLORABLE.\n";
}
return 0;
}
Comments
Post a Comment