二分图判断(染色法)

程序员文章站 2024-03-17 15:08:46

...

二分图判断(染色法)

二分图：
设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。

染色判断：
二分图判断可分为：连通图判断和非连通图判断
染色思路:
1)初始所有定点未染色
2)随意取出一个未染色的顶点u,把它染成一种颜色(假设为0)。
3)取出与它连接的结点v,如果v未染色，则将v染成和u不同的颜色(假设为1)，如果v已经染色，那么判断u和v颜色是否相同，相同则表明染色失败，该图不是二分图，结束。
4）遍历所有结点，重复步骤3)
5)连通图只需要一次dfs染色，非连通图则多次dfs染色。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5+100;
struct Edge{
    int to,next;
}edge[maxn<<1];
int n,m;
int head[maxn],tot,color[maxn];
bool ok;
void init(){
    memset(head,-1,sizeof(head));
    memset(color,-1,sizeof(color));
    tot = 0;
}

inline  void addedge(int u,int v){
   edge[tot].to = v;
   edge[tot].next = head[u];
   head[u] = tot++;
}

void dfs(int u,int col){
    color[u] = col;
    for(int i=head[u];~i;i=edge[i].next){
        int v = edge[i].to;
        if(color[v]==color[u]){
            ok = false;
            return ;
        }
        if(color[v]==-1){
            dfs(v,col^1);
            if(!ok) return ;
        }
    }
}

int main(){
    int u,v;
    while(~scanf("%d%d",&n,&m)){
        init();
        for(int i=0;i<m;++i){
            scanf("%d%d",&u,&v);
            addedge(u,v);
            addedge(v,u);
        }
        ok = true;
        /*连通图*/
        //dfs(1,0);
        /*非连通图*/
        for(int i=1;i<n;++i){
            if(color[i]==-1){
                dfs(i,0);
                if(!ok) break;
            }
        }
        printf("%s\n",ok?"YES":"NO");
    }
}

讲完理论，来点题目练练手。
例题：
codeforce 1093D

题意:T组样例，每次给出n个顶点m条边的无向图，将整个图的所有顶点填充数字，每个顶点u可填数字1，2，3. 要求m条边每条边连接的两个顶点(u,v)的填充的数字权值之和为奇数。提问这样的填充方法有多少个。方案可能很大，需要取模998244353。
如果没有则输出0.

思路: m条边每条边上连接两个顶点都满足题意，简单举例对于图：1-2->3->4，顶点集合V={1 3} 填奇数，E={2，4}填偶数或者反过来都可以满足题意。由此我们想到将原图G划分为两个互不相交顶点集V，E，两个顶点集合中顶点个数分别为x,y.那么若顶点集合V中全部填奇数（1，2），E中全部填偶数2.便有2^x 种方法。反过来V填偶数，E填奇数便有2^y 种方案，一个二分图便有2^x + 2^y 种方案。注意题目中可能是非连通图，即存在多个二分子图，那么答案就是对这多个子图方案累乘即可。不懂看代码便知道。

AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5+100;
const ll mod = 998244353;
struct Edge{
    int to,next;
}edge[maxn<<1];
int n,m,x,y;
int head[maxn],tot,color[maxn];
int pw[maxn];
bool ok;
void init(){
    memset(head,-1,sizeof(head));
    memset(color,-1,sizeof(color));
    tot = 0;
}

inline  void addedge(int u,int v){
   edge[tot].to = v;
   edge[tot].next = head[u];
   head[u] = tot++;
}

void dfs(int u,int col){
    color[u] = col;
    if(col==1) ++x;
    else ++y;
    for(int i=head[u];~i;i=edge[i].next){
        int v = edge[i].to;
        if(color[v]==color[u]){
            ok = false;
            return ;
        }
        if(color[v]==-1){
            dfs(v,col^1);
            if(!ok) return ;
        }
    }
}

int main(){
    int T,u,v;
    pw[0] = 1;
    pw[1] = 2;
    for(int i=2;i<maxn;++i){
        pw[i] = pw[i-1]*2LL%mod;
    }
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=0;i<=n;++i){
            head[i] = color[i] = -1;
        }
        for(int i=0;i<m;++i){
            scanf("%d%d",&u,&v);
            addedge(u,v);
            addedge(v,u);
        }
        ok = true;
        ll ans = 1;
        for(int i=1;i<=n;++i){
            if(color[i]==-1){
                x = 0;
                y = 0;
                dfs(i,0);
                ans = ans*((pw[x]+pw[y])%mod)%mod;
                if(!ok){
                    break;
                }
            }
        }
        if(ok){
            cout<<ans<<endl;
        }
        else{
            puts("0");
        }
    }
    return 0;
}

牛客 Graph coloring I

题意:给定n个顶点m条边的无向图，判断是否能将图相邻的顶点染成不同的颜色，若能，输出每个点染的颜色，0，1表示不同颜色。若不能，查找是否存在一个简单奇数环，输出这个奇数环，环起点终点任意。两种情况都不能则输出-1。

思路:
第一种情况显然是裸的二分图染色问题。
重点讲第二种情况一下奇数环。
**

定理:二分图和奇数环互斥。

证明: 假设二分图是一个奇数环。
假设一个环 u1,u2,u3,…u(2i-1)(i>=1且i为正整数)。相邻顶点存在边连接，u1，u(2i-1)也存在边连接。
由二分图的定义我们可以知道u1,u2在两个不同的顶点集合V,E中，u2，u3在E，V中，我们可以得出奇数顶点在集合V中，偶数顶点在E中。那u1，u(2*i-1)在同一个集合中，由二分图的定义，同一个集合中顶点不相交，矛盾。
所以二分图和奇数环互斥。

所以二分图判断即可，出现相邻结点颜色相同代表出现奇环。color[v]==color[u] 那么便可以以u为起点，v为终点，另外开一个fa数组记录v的父亲结点。

详见AC代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5+100;
struct Node{
    int to,next;
};
Node edge[maxn<<1];
int n,m;
int tot,st,ed;
int head[maxn],fa[maxn],a[maxn],b[maxn];

void init(){
   tot = 0;
   memset(head,-1,sizeof(head));
   memset(a,-1,sizeof(a));
}
inline  void addedge(int u,int v){
   edge[tot].to = v;
   edge[tot].next = head[u];
   head[u] = tot++;
}

bool dfs(int u,int color){
    a[u] = color;
    for(int i=head[u]; ~i; i=edge[i].next){
        int v = edge[i].to;
        if(v==fa[u]) continue;
        if(~a[v]){
            if(a[v]!=a[u]) continue;
            else{
                st = u, ed = v;
                return false;
            }
        }
        fa[v] = u;
        if(!dfs(v,!color)) return false;
    }
    return true;
}

int main(){
    int u,v;
    scanf("%d%d",&n,&m);
    init();
    for(int i=1;i<=m;++i){
        scanf("%d%d",&u,&v);
        addedge(u,v);
        addedge(v,u);
    }
    if(dfs(1,0)){
        printf("0\n");
        for(int i=1;i<n;++i){
            printf("%d ",a[i]);
        }
        printf("%d\n",a[n]);
    }
    else{
        int k = 0;
        b[k++] = ed;
        for(int i=st;i!=ed;i=fa[i]){
            b[k++] = i;
        }
        printf("%d\n",k);
        for(int i=0;i<k-1;++i){
            printf("%d ",b[i]);
        }
        printf("%d\n",b[k-1]);
    }
    return 0;
}

**暂且就这么多，找到好的题目继续分享。

二分图判断(染色法)