G7021 [GESP202606 七级] 染色 题解

知识点：二分图判定、奇环、图的染色。

解题思路

对所有连通分量尝试二染色，若出现同色相邻则输出3，否则输出2。

为什么正确

题目每点度2，因此各分量均为环；偶环可2染，奇环不可2染但必可3染，检测二分性足以得到最少颜色数。

易错点

不能把任意非二分图都断言3色，本结论依赖每点度2；需处理所有分量。

复杂度

每组时间O(n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--) {
        int n;
        cin>>n;
        vector<vector<int>>g(n+1);
        for(int i=0;i<n;i++) {
            int u,v;
            cin>>u>>v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        vector<int>c(n+1,-1);
        bool ok=true;
        for(int s=1;s<=n;s++)if(c[s]<0) {
            vector<int>q= {
                s
            }
            ;
            c[s]=0;
            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;
                q.push_back(v);
            }
            else if(c[v]==c[q[k]])ok=false;
        }
        cout<<(ok?2:3)<<"\n";
    }
}

说明

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