2020.03.01

因为今天刚接触,所以先写写二分图的定义以及简单的判定。

题目链接


首先,什么是二分图?

图的定义相信大家都知道。这里就以无向图作为例子。

而二分图是一种特殊的图,在这种图中,我们可以把所有点分成恰好2个集合,而图中所有的边都在这两个集合的点之间,也就是同一个集合中的点之间不能有任何连接。

举个栗子。

比如这样的一张图就是一个二分图。我们可以把4个顶点分为{1,2}和{3,4}​,每个集合中的元素没有相互连接的。


了解了定义,那我们就要来了解如何判定二分图了。

常用的一种方法叫做染色法

这种方法是把所有点都分为2个颜色,首先假设这是一张二分图。那么,每一对相连的点的颜色都应该是不同的。所以我们可以把两种颜色都赋予一个值,分别为1和-1

然后所有点的初始状态都是没有颜色的,我们先从第一个点开始,给它染上颜色1。然后再把所有和它相连的点染上颜色-1,这个很容易理解,有连接的两个点不应该在同一个集合中。

如果要染色的点已经有颜色了,并且和当前这个点的颜色相同,那么说明发生了矛盾,也就是这张图不是二分图。


我们在具体数据上进行一下模拟。

(前面的序号表示递归层数,从0开始,以$dfs$为例)

0.将结点1的颜色修改为1

1.将结点2的颜色修改为-1

2.将结点4的颜色修改为1

3.将结点5的颜色修改为-1

2.在将结点5的颜色修改为1时发现结点5的颜色为-1,这张图不是二分图。

所以,只需要照着$dfs$的思路轻松把它实现出来就好了。


code

#include<bits/stdc++.h>
#define maxn 100011
using namespace std;
typedef long long ll;
struct node
{
    ll v,nxt;
}e[maxn<<1|1];
ll cnt=0,head[maxn],c[maxn];
//0:无色 1:颜色1 -1:颜色2
void add(ll u,ll v)
{
    e[++cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
bool dfs(ll u,ll cur)
{
    c[u]=cur;
    for(ll i=head[u];i;i=e[i].nxt)
    {
        ll v=e[i].v;
        if(!c[v])
        {
            if(dfs(v,-cur))return 1;
        }  
        else if(c[v]==cur)return 1;
    }
        
    return 0;
}
int main()
{
    ll n,m;
    cin>>n>>m;
    for(ll i=1;i<=m;i++)
    {
        ll u,v;
        cin>>u>>v;
        add(u,v),add(v,u);
    }
    bool flag=0;
    for(ll i=1;i<=n;i++)
        if(!c[i])flag|=dfs(i,1);
    puts(flag?"No":"Yes");
    return 0;
}
最后修改:2020 年 05 月 01 日 04 : 59 PM