要求判斷能否對一個給定的圖這樣著色：只用紅色和黑色；相鄰結點顏色不相同。
BFS，遍歷 + 染色 + 檢測。
以下是我的代碼：
#include<iostream>
#include<string.h>
#define maxn 207
using namespace std;
typedef struct
{
long counter,front,rear,item[maxn];
}queue;
void Clear(queue &q)
{
q.counter=0;q.front=0;q.rear=-1;
}
bool Empty(queue &q)
{
return (q.counter==0);
}
void Push(queue &q,long x)
{
q.counter++;q.rear++;q.item[q.rear]=x;
}
void Pop(queue &q,long &x)
{
q.counter--;x=q.item[q.front];q.front++;
}
long n,m;
bool g[maxn][maxn];
bool bicolorable()
{
long st[maxn];
bool used[maxn];
queue q;
Clear(q);
memset(st,-1,sizeof(st));
memset(used,false,sizeof(used));
Push(q,1);st[1]=0;used[1]=true;
while(!Empty(q))
{
long u;Pop(q,u);
for(long v=1;v<=n;v++)
if(g[u][v])
{
if(st[v]!=-1&&st[u]+st[v]!=1)
return false;
if(!used[v])
{
Push(q,v);st[v]=1-st[u];used[v]=true;
}
}
}
return true;
}
int main()
{
while(cin>>n)
{
if(n==0) break;
memset(g,false,sizeof(g));
cin>>m;
for(long i=1;i<=m;i++)
{
long u,v;
cin>>u>>v;
u++;v++;
g[u][v]=g[v][u]=true;
}
// Input
if(bicolorable())
// BFS
cout<<"BICOLORABLE."<<endl;
else cout<<"NOT BICOLORABLE."<<endl;
// Output
}
return 0;
}
posted on 2010-11-12 22:40
lee1r 閱讀(456)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：圖論