大家好，我是энтджей，今天是我2026年第二十一次正式发题解！

2026年发布的题解！

能不能点个赞

---

首先简化题意：

• 简单来说捏就是给定一个图，然后给他染色，要求相邻的两个点颜色不同

然后就是写代码:

• 这道题我认为是六级里最简单的题了，场上10分钟切掉：
  • 根据分析，可以得知：
    • 当一个子图连通时：
      • 当这个子图有偶数个点时，需要2种颜色交替进行（ABAB……AB）
      • 当这个子图有奇数个点时，需要3种颜色（因为开头和结尾的颜色会重复，即（ABAB……ABC））
    • 特别的：
      • 当只有0个点需要0种颜色
      • 当只有1个点需要1种颜色
      • 当只有2个点需要2种颜色

最后输出（write）：

• 输出每个图拆分成子图后所有子图所需要的最大颜色数

完整代码：

#include<bits/stdc++.h>
#define int long long  
using namespace std;
const int N = 1e6 + 10;
const int INF = 1e18;
int n, cnt, T;
vector<int> g[N];
bool vis[N];
void init() {
    for(int i = 1; i <= n; i++) {
        清空g[i]
    }
    初始化vis
}
void dfs(int u) {
    子图结点数自增
    标记为以访问
    for( auto v : g[u] ) {
        如果与他相连的结点为访问则进行DFS
    }
}
void solve() {
    init();
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int u, v;
        cin >> u >> v;
        建边
    }
    int maxn = 0;
    for(int i = 1; i <= n; i++) {
        if(为访问) {
            cnt = 0;
            dfs(i);
            更新最大值
        }
    }
    输出最大值
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

---

🎉完结撒花🎉