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;
}

分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *