欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分图判断(染色法)

程序员文章站 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;
}

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

相关标签: 二分图