题解

楼上的，我只用了29分钟59秒[手动狗头]
思路：
按照题目要求，这道题的答案只可能是2或3，所以我们可以直接邻接矩阵使用邻接表存图，再使用广搜遍历每一个环，最后如果有环是单数个节点就输出3，反之输出2。

#include<bits/stdc++.h>
using namespace std;
const int mn = 1e5+9;
bool vis[mn];
int bfs(int x,vector<int>ve[mn]){
    queue<int>q;
    int cnt=1;
    q.push(x);
    vis[x] = 1;
    while(q.size()){
        int r = q.front();
        q.pop();
        for(int y:ve[r]){
            if(!vis[y]){
                cnt++;
                vis[y] = 1;
                q.push(y);
            }
        }
    }
    if(cnt%2==1)return 1;
    return 0;
}
int main(){
    int t;
    cin >> t;
    while(t--){
        int n;
        vector<int>ve[mn];
        int a[mn];
        cin >> n;
        for(int i=1;i<=n;i++){
            int u,v;
            cin >> u >> v;
            ve[u].push_back(v);
            ve[v].push_back(u);
        }
        memset(vis,0,sizeof(vis));
        int num=0;
        for(int i=1;i<=n;i++){
            if(!vis[i]){
                num = max(bfs(i,ve),num);
            }
        }
        cout << (num%2==1?3:2) << endl;
    }
    return 0;
}

求赞
[手动狗头][手动狗头][手动狗头]
[手动点赞][手动点赞][手动点赞]