二分图的染色法判定

二分图的染色法判定

二分图的定义：如果一张无向图的 $n$ 个顶点可以分为 $A,B$ 两个不相交的集合，并且同一集合内的所有点之间没有边相连，记这张特征图为二分图

$\implies$ 每一条边都是连接两个集合的边，所以从一个集合出发需要经过偶数条边才能走回原来的集合

推理：二分图不存在奇环（边数为奇数的环）

二分图的判定：染色法，用两种不同的颜色标记整张图，当一个节点被颜色 $1$ 标记后，那么它相邻的节点会被标记颜色 $2$ ，如果标记过程中，存在颜色冲突，那么图中存在奇环

int n,m;
vector<int> e[N];

cin>>n>>m;
for (int i=1;i<=m;i++) {
    int u,v;
    cin>>u>>v;
    e[u].push_back(v);
    e[v].push_back(u);
}

因为不考虑每条边的边权，所以之间利用 vector<int> e[N] 存图，e[u]=v 表示 $u$ 点到 $v$ 点存在一条边

然后 DFS 对每个点尝试染色

int color[NN];//0表示没有被染色

bool dfs(int u,int c){//走到u点应该染c表示的颜色
    color[u]=c;
    for (auto v:e[u]){//遍历u点的邻点
        if (!color[v]){//如果没有被染色
            if (dfs(v,3-c)){//走到v点，dfs染3-c表示的颜色，c=1，3-c=2 c=2,3-c=1
                return 1;//如果dfs递归后为1，向上回溯1表示存在奇环
            }
        }
        if (color[v]==c)//如果冲突，递归结束，返回1，表示存在负环
            return 1;
    }
    return 0;//0表示不存在奇环
}

对每个没有被染色的点进行一次 DFS ，直到整张图都被染色

bool f=0;//判断是否存在奇环
for (int i=1;i<=n;i++){
    if (!color[i]){//如果没有被染色，那么从这个点开始dfs
        if (dfs(i,1)){
            f=1;
            break;
        }
    }
}

例如洛谷P1330

题目要求的是找到最少的河蟹数量，使得每条边至少有一个端点被覆盖（河蟹占据），并且相邻的两个点不能同时有河蟹

这实际上等价于求图的一个顶点覆盖，且覆盖的顶点集合是一个独立集

所以需要记录每次 DFS 过程中两种颜色点的数量，取最小的累加答案

int n,m;
vector<int> e[10010];
int color[10010];
int ans,cnt1,cnt2;

bool dfs(int u,int c){
    color[u]=c;
    if (c==1) cnt1++;
    else cnt2++;
    for (auto v:e[u]){
        if (!color[v]){
            if (dfs(v,3-c)){
                return 1;
            }
        }
        if (color[v]==c)
            return 1;
    }
    return 0;
}

int main()
{
    cin>>n>>m;
    for (int i=1;i<=m;i++) {
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    
    bool f=0;
    for (int i=1;i<=n;i++){
        if (!color[i]){
            cnt1=0,cnt2=0;
            if (dfs(i,1)){
                f=1;
                break;
            }
            ans+=min(cnt1,cnt2);
        }
    }
    if (f) cout<<"Impossible";
    else cout<<ans;
    return 0;
}