二分图判断
博客专区 > Airship 的博客 > 博客详情
二分图判断
Airship 发表于4个月前
二分图判断
  • 发表于 4个月前
  • 阅读 3
  • 收藏 0
  • 点赞 0
  • 评论 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;  
}  

 

共有 人打赏支持
粉丝 29
博文 718
码字总数 18433
×
Airship
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: