G7003 [GESP202403 七级] 交流问题 题解

知识点：二分图、连通分量、计数。

解题思路

逐连通分量进行二染色，统计两侧人数。由于每个分量的两种身份可以整体互换，最少人数累加较小侧，最多累加较大侧。

为什么正确

约束只连接分量内部，同一分量的相对身份由二染色固定；分量间独立选择朝向，极值可分别相加。

易错点

当前解利用题目约束可满足二分关系；孤立点也组成一个分量，贡献最小0、最大1。

复杂度

时间O(n+m)，空间O(n+m)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<vector<int>>g(n+1);
    while(m--) {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int>c(n+1,-1);
    int lo=0,hi=0;
    for(int s=1;s<=n;s++)if(c[s]<0) {
        int cnt[2]= {
            1,0
        }
        ;
        c[s]=0;
        vector<int>q= {
            s
        }
        ;
        for(int k=0;k<(int)q.size();k++)for(int v:g[q[k]])if(c[v]<0) {
            c[v]=c[q[k]]^1;
            cnt[c[v]]++;
            q.push_back(v);
        }
        lo+=min(cnt[0],cnt[1]);
        hi+=max(cnt[0],cnt[1]);
    }
    cout<<lo<<" "<<hi;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。