文档章节

【BFS】CODE[VS] 1535 封锁阳光大学(二分图BFS染色)

Fograin
 Fograin
发布于 2016/11/02 12:26
字数 355
阅读 10
收藏 0

点击进入异世界


关于二分图染色详情请回戳我的上一篇博文【DFS】CODE[VS] 1535 封锁阳光大学 (二分图染色)

BFS代码也很好写,思路跟DFS基本一样,只不过在搜的时候,我们要从一个点出发遍历完整个连通子图

基本的BFS

代码如下(略丑,比DFS慢一些):

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

const int maxn = 320010;

using namespace std;

int tot;
int ans;
int n,m;
int color[maxn];
int head[maxn];
int sum[3];
bool motherfucker;
bool vis[maxn];

struct node{
    int f;
    int t;
    int next;
}e[maxn << 1];

inline void build(int ff,int tt)
{
    tot++;
    e[tot].f = ff;
    e[tot].t = tt;
    e[tot].next = head[ff];
    head[ff] = tot;
}

queue<int >q;

void bfs(int s)
{
    q.push(s);
    vis[s] = 1;
    color[s]= 1;
    sum[1]++;
    while(!q.empty())
    {

        int u = q.front();
        if(u == 0)
            continue;
        q.pop();
        for(int i = head[u];i != -1;i = e[i].next)
        {
            int v = e[i].t;
            if(v == 0)
                continue;
            if(vis[v] == 0)
            {
                if(color[u] == 1)
                {   
                    color[v] = 2;
                    sum[2]++;
                    vis[v] = 1;
                    q.push(v);
                }
                else if(color[u] == 2)
                {
                    color[v] = 1;
                    sum[1]++;
                    vis[v] = 1;
                    q.push(v);
                }

            }
            else
            {
                if(color[v] == color[u])
                {
                    motherfucker = 1;
                }   
            }

        }   
    }
}

int main()
{
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        build(a,b);
        build(b,a);
    }
    vis[0] = 1;
    for(int i = 1;i <= n;i++)
    {
        sum[1] = sum[2] = 0;
        if(vis[i] == 0)
        {
            bfs(i);
            ans += min(sum[1],sum[2]);
        }   
    }
    if(motherfucker == 1)
    {
        printf("Impossible\n");
        return 0;
    }
    printf("%d\n",ans);

return 0;
}


THE END

By Peacefuldoge

http://blog.csdn.net/loi_peacefuldog

© 著作权归作者所有

Fograin
粉丝 0
博文 22
码字总数 16052
作品 0
莱芜
程序员
私信 提问
洛谷 P1330 封锁阳光大学 【思维 + 二分图判定】

版权声明:本文为博主原创文章,喜欢就点个赞吧 https://blog.csdn.net/Anxdada/article/details/82627917 传送门 题意: 可以占领一点, 然后和这个点相邻的边都被封锁了, 如果在占领的这一点...

Anxdada
2018/09/11
0
0
Codeforces 题目合集+分类+蒟蒻的代码 【Updating...】【167 in total】

894A - QAQ 暴力 http://paste.ubuntu.com/26011561/ 894B - Ralph And His Magic Field 数学 http://paste.ubuntu.com/26011566/ 894C - Marco and GCD Sequence 构造 http://paste.ubuntu.......

my_sunshine26
2017/07/29
0
0
二分图算法模板以及相关知识

说说二分图,其实图论的题难点不在用算法,难在如何建图,只有图建好了,剩下的就简单了,在这说说求二分图的算法,即匈牙利算法,其实一点都不难,也很好理解拿笔写写就行了. //板子, 直接套就行 //...

Anxdada
2017/06/22
0
0
[HAOI2017] 新型城市化

给出的图中恰包含2个团,则图的补图为一个二分图,其最大独立集为原图的最大团。 我们知道,二分图的最大独立集=V-最小顶点覆盖,最小顶点覆盖=最大匹配。 问题转化为:计算删去后最大匹配减...

nosta
2018/12/24
0
0
2018年12月份冬季PAT甲级考试总结

版权声明:转载请告知博主并要注明出处嗷~ https://blog.csdn.net/AkatsukiItachi/article/details/84931516 终于从威海回到学校了,可以平复一下想打死自己的心情写一下总结了。 本来打算这...

语海与冰
2018/12/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

0.01-Win10安装linux子系统

一、安装Debian子系统 -1、控制面板设置: -1.1、打开“控制面板” —— “程序” —— “启用或关闭Windows功能” —— 勾选 “适用于Linux的Windows子系统” -2、设置: -2.1、打开“设置”...

静以修身2025
昨天
2
0
init 0-6 (启动级别:init 0,1,2,3,4,5,6)

启动级别: init 0,1,2,3,4,5,6 这是个很久的知识点了,只是自己一直都迷迷糊糊的,今天在翻出来好好理解下。。 0: 停机 1:单用户形式,只root进行维护 2:多用户,不能使用net file system...

圣洁之子
昨天
2
0
Android Camera HAL浅析

1、Camera成像原理介绍 Camera工作流程图 Camera的成像原理可以简单概括如下: 景物(SCENE)通过镜头(LENS)生成的光学图像投射到图像传感器(Sensor)表面上,然后转为电信号,经过A/D(模数转...

天王盖地虎626
昨天
2
0
聊聊Elasticsearch的ProcessProbe

序 本文主要研究一下Elasticsearch的ProcessProbe ProcessProbe elasticsearch-7.0.1/server/src/main/java/org/elasticsearch/monitor/process/ProcessProbe.java public class ProcessProb......

go4it
昨天
3
0
mysql PL(procedure language)流程控制语句

在MySQL中,常见的过程式SQL语句可以用在存储体中。其中包括IF语句、CASE语句、LOOP语句、WHILE语句、ITERATE语句和LEAVE语句,它们可以进行流程控制。 IF语句相当于Java中的if()...else if(...

edison_kwok
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部