1. 实现二分图的判定

怎么判断一个图是否是二分图呢？其实很简单。

1. 对于一个图，我们任意选中图中一个未被选中过的点（默认为未被选中过），标记为选中过了，加入到处理队列中。然后枚举它相邻的所有点。
2. 如果当前枚举的点未被选中过，则把当前枚举的点标记为与当前选中的点不一样的颜色，标记为选中过了，然后加入到处理队列中。
3. 如果当前枚举的点被选中过了且颜色与当前选中的点颜色不同，则跳过当前枚举的点。
4. 如果当前枚举的点被选中过了且颜色与当前选中的点颜色相同，则说明这个图不是二分图（得到答案），结束程序。
5. 如果与当前选中的点相邻的点都已经被选中过了，而且没有发现颜色与当前选中的点颜色相同的，则从处理队列中去掉当前选中的点（pop 操作）。
6. 如果队列为空且所有的点都被选中过了，则说明这个图是二分图（得到答案），结束程序。
7. 如果当前队列不为空，则选中处理队列中的第一个点，重新执行第二步。

整个过程用 BFS 实现，简单流程而自然～

2. 模板题以及题解

HDU-1121：传送门
思路：模板题，判断是否是二分图，是就输出 Correct，否则输出 Wrong。

代码：

#include <bits/stdc++.h>
using namespace std;
int t,n,m;
bool book[10005],color[10005];
int main()
{
    ios::sync_with_stdio(0);
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        vector<int> g[10005];queue<int> que;bool istrue=1;
        for(int i=1;i<=n;i++)book[i]=color[i]=0;
        for(int i=1,u,v;i<=m;i++)cin>>u>>v,g[u].push_back(v),g[v].push_back(u);
        for(int i=1;i<=n&&istrue;i++)
            if(!book[i])
            {
                book[i]=1,que.push(i);
                while((!que.empty())&&istrue)
                {
                    int qf=que.front();que.pop();
                    for(vector<int>::iterator it=g[qf].begin();it!=g[qf].end();it++)
                        if(book[*it]){if(color[*it]==color[qf]){cout<<"Wrong"<<endl,istrue=0;break;}}
                        else book[*it]=1,color[*it]=color[qf]^1,que.push(*it);
                }
            }
        if(istrue)cout<<"Correct"<<endl;
    }
    return 0;
}