心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0
要求判断能否对一个给定的图这样着色:只用红色和黑色;相邻结点颜色不相同。
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==0break;
       
       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 阅读(450) 评论(0)  编辑 收藏 引用 所属分类: 题目分类:图论

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理