题意：给一张图，判断是不是二分图；
自己一开始不知道是二分图染色，理解的是任意三点不能互相连接
可能以后遇到这样的模型，可以往二分图想；
首先怎么判定一个图是否为二分图
从其中一个定点开始，将跟它邻接的点染成与其不同的颜色，最后如果邻接的点有相同颜色，则说明不是二分图；
每次用bfs遍历即可；
下面这个算是模板：解释的比较详细。
#include <queue>
#include <cstring>
#include <iostream>
using namespace std; const int N = ;
int col[N], Map[N][N]; //0为白色，1为黑色
bool BFS(int s, int n)
{
queue<int> p;
p.push(s);
col[s] = ; //将搜索起始点涂成黑色
while(!p.empty())
{
int from = p.front();
p.pop();
for(int i = ; i <= n; i++)
{
if(Map[from][i] && col[i] == -) //如果从from到i的边存在（为邻接点） && i点未着色
{
p.push(i); //将i点加入队列
col[i] = !col[from];//将i点染成不同的颜色
}
if(Map[from][i] && col[from] == col[i])//如果从from到i的边存在（为邻接点）
return false; //并且 i点和from点这一对邻接点颜色相同，
} // 则不是二分图
}
return true; //搜索完s点和所有点的关系，并将邻接点着色，且邻接点未发现相同色则返回true
} int main()
{
int n, m, a, b;
memset(col, -, sizeof(col));
cin >> n >> m; //n 为有多少点，m为有多少边
for(int i = ; i < m; i++)
{
cin >> a >> b;
Map[a][b] = Map[b][a] = ;
}
bool flag = false;
for(i = ; i <= n; i++) //遍历并搜索各个连通分支
{
if(col[i] == - && !BFS(i, n)) //每次找没有着色的点进行判断，如果从它开始BFS发现相同色邻接点则不是二分图
{
flag = true;
break;
}
}
if(flag)
cout << "NO" <<endl;
else
cout << "YES" <<endl;
return ;
}
自己的本题ac代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue> using namespace std;
int n,m,book[],mp[][];
void init(){
memset(book,-,sizeof(book));
memset(mp,,sizeof(mp));
}
bool bfs(int s)
{
queue <int> q;
q.push(s);
book[s]=;
while(!q.empty())
{
int from = q.front();
q.pop();
for(int i=;i<n;i++)
{
if(mp[from][i]&&book[i]==-)
{
q.push(i);
book[i] = !book[from];
}
if(mp[from][i]&&book[i]==book[from])
{
return false;
}
}
}
return true;
}
int main(){
while(~scanf("%d",&n),n){
scanf("%d",&m);
init();
for(int i=;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
mp[x][y]=;
mp[y][x]=;
}
bool flag = true;
for(int i=;i<n;i++)
{
if(book[i]==-&&!bfs(i))
{
flag=false;
break;
}
}
if(flag)puts("BICOLORABLE.");
else puts("NOT BICOLORABLE.");
}
return ;
}