文档章节

二分图判断

Airship
 Airship
发布于 2017/09/08 09:59
字数 635
阅读 6
收藏 0

题目:http://acm.hdu.edu.cn/showproblem.php?pid=2444

 

题意:给定一个无向图,先判断它是否是二分图,如果是则求出最大匹配,否则输出“No”。

 

二分图是这样一个图: 有两顶点集且图中每条边的的两个顶点分别位于两个顶点集中,每个顶点集中没有边相连接!

判断二分图的常见方法:开始对任意一未染色的顶点染色,之后判断其相邻的顶点中,若未染色则将其染上和相邻顶点不同的颜色, 若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图,若颜色不同则继续判断,用深搜即可。因为是无向二分图的匹配,所以要除以2。

题目:http://acm.hdu.edu.cn/showproblem.php?pid=2444
 
题意:给定一个无向图,先判断它是否是二分图,如果是则求出最大匹配,否则输出“No”。

二分图是这样一个图: 有两顶点集且图中每条边的的两个顶点分别位于两个顶点集中,每个顶点集中没有边相连接!
判断二分图的常见方法:开始对任意一未染色的顶点染色,之后判断其相邻的顶点中,若未染色则将其染上和相邻顶点不同的颜色, 若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图,若颜色不同则继续判断,用深搜即可。因为是无向二分图的匹配,所以要除以2。

[cpp] view plain copy
#include <iostream>  
#include <string.h>  
#include <stdio.h>  
  
using namespace std;  
const int N = 2005;  
  
int head[N],link[N];  
bool vis[N],col[N];  
int cnt,n,m;  
  
struct Edge  
{  
    int to;  
    int next;  
};  
  
Edge edge[N*N];  
  
void Init()  
{  
    cnt = 0;  
    memset(head,-1,sizeof(head));  
    memset(col,0,sizeof(col));  
}  
  
void add(int u,int v)  
{  
    edge[cnt].to = v;  
    edge[cnt].next = head[u];  
    head[u] = cnt++;  
}  
  
bool Color(int u)  
{  
    for(int i=head[u]; ~i; i=edge[i].next)  
    {  
        int v = edge[i].to;  
        if(!col[v])  
        {  
            col[v] = !col[u];  
            if(!Color(v)) return false;  
        }  
        else if(col[v] == col[u])  
            return false;  
    }  
    return true;  
}  
  
bool dfs(int u)  
{  
    for(int i=head[u]; ~i; i=edge[i].next)  
    {  
        int v = edge[i].to;  
        if(!vis[v])  
        {  
            vis[v] = 1;  
            if(link[v] == -1 || dfs(link[v]))  
            {  
                link[v] = u;  
                return true;  
            }  
        }  
    }  
    return false;  
}  
  
int match()  
{  
    int ans = 0;  
    memset(link,-1,sizeof(link));  
    for(int i=1; i<=n; i++)  
    {  
        memset(vis,0,sizeof(vis));  
        if(dfs(i)) ans++;  
    }  
    return ans;  
}  
  
int main()  
{  
    while(~scanf("%d%d",&n,&m))  
    {  
        if(n == 1)  
        {  
            puts("No");  
            continue;  
        }  
        Init();  
        while(m--)  
        {  
            int u,v;  
            scanf("%d%d",&u,&v);  
            add(u,v);  
            add(v,u);  
        }  
        col[1] = 1;  
        if(!Color(1))  
        {  
            puts("No");  
            continue;  
        }  
        printf("%d\n",match()>>1);  
    }  
    return 0;  
}  

 

本文转载自:http://blog.csdn.net/acdreamers/article/details/8650811

共有 人打赏支持
Airship
粉丝 39
博文 908
码字总数 19854
作品 0
南京
高级程序员
私信 提问
洛谷P1525 关押罪犯 【思维 + 二分图判定】

版权声明:本文为博主原创文章,喜欢就点个赞吧 https://blog.csdn.net/Anxdada/article/details/82831861 传送门 题意: 给出m对憎恨关系, 有一个憎恨值, 现在要将这n个人分成两堆人, 要求这...

Anxdada
09/24
0
0
二分图算法模板以及相关知识

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

Anxdada
2017/06/22
0
0
复杂网络分析库NetworkX学习笔记(5):二分图

二分图又称二部图,是图论中的一种特殊模型,它的顶点可分割为两个互不相交的子集,并且图中的每条边所关联的两个顶点分别属于这两个不同的顶点集。二分图在复杂网络分析中有很多应用,例如科...

鉴客
2012/11/03
1K
0
[BZOJ2709] [Violet 1]迷宫花园

http://www.lydsy.com/JudgeOnline/problem.php?id=2709 这题是权限题,版权问题不放题意,我来简要的说一下: 给出一个迷宫,有起始点终点,可以上下左右走,移动的耗时是1,可以改变上下走...

CABI_ZGX
02/03
0
0
司机乘客匹配中的距离和最小问题

这个是在工作中遇到的一个实际的算法问题,问题描述如下,当前有m个司机,n个乘客,每个司机和每个乘客的距离由经纬度可以计算得到,如何匹配可以使其去接乘客的距离和最小?(只能一个司机接...

necther
05/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

oh-my-zsh 自定义

GitHub 地址 基于 oh-my-zsh 的自定义配置,增加了一些个人常用插件与皮肤。 采用的是 git submodule 来维护,包括 oh-my-zsh,之所以这么搞,主要是手头有多台 linux 需要维护, 每台机器、...

郁也风
今天
6
0
Docker安装踩坑:E_FAIL 0x80004005的解决

参考 菜鸟教程--Windows Docker 安装 http://www.runoob.com/docker/windows-docker-install.html 官方文档-Install Docker Toolbox on Windows https://docs.docker.com/toolbox/toolbox_in......

karma123
今天
5
0
js垃圾回收机制和引起内存泄漏的操作

JS的垃圾回收机制了解吗? Js具有自动垃圾回收机制。垃圾收集器会按照固定的时间间隔周期性的执行。 JS中最常见的垃圾回收方式是标记清除。 工作原理:是当变量进入环境时,将这个变量标记为“...

Jack088
昨天
17
0
大数据教程(10.1)倒排索引建立

前面博主介绍了sql中join功能的大数据实现,本节将继续为小伙伴们分享倒排索引的建立。 一、需求 在很多项目中,我们需要对我们的文档建立索引(如:论坛帖子);我们需要记录某个词在各个文...

em_aaron
昨天
27
0
"errcode": 41001, "errmsg": "access_token missing hint: [w.ILza05728877!]"

Postman获取微信小程序码的时候报错, errcode: 41001, errmsg: access_token missing hint 查看小程序开发api指南,原来access_token是直接当作parameter的(写在url之后),scene参数一定要...

两广总督bogang
昨天
33
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部