背景：

原题链接
上次七级两道题都是10分，总分55没过。这次终于做出这一道题，第二题消消乐0分，总分69分终于过了，写题解纪念一下。

---

思路：

$G$中恰好有$n$条边，说明$G$是一个或多个环，要使得任意一条边两端的结点都有不同的颜色且需要颜色最少，显然要按一定规则染色。

如果该环节点数为奇数，那么这样染色需要颜色最少：

最少要$\boxed{3}$种颜色。

如果该环节点数为偶数，那么这样染色需要颜色最少：

最少要$\boxed{2}$种颜色。

所以，综上所述，我们可以先把图按无向图用邻接表储存起来，再建立$vis$数组，将节点从$1$到$n$遍历，如果没有访问过，就说明这是一个新的环，则用搜索遍历一遍整个环，并用$cnt$记录环的节点数，如果是奇数答案就是$3$，偶数就是$2$。由于可能不止一个环，所以无论$3$还是$2$答案都取最大值。将所有结点遍历过后，输出答案。

注意，由于$G$中有多个环，而且有$T$组数据，所以要用到多个$vis$数组、邻接表和广搜遍历用的队列，但由于数据范围$3\leq n \leq10^5$，所以不可能每次都开一个局部$vis$数组、邻接表和队列，会MLE，所以每次用完后要初始化（队列每次为空才结束遍历，所以不用特殊处理，另外两个要）。

---

代码：

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
bool vis[100010];//vis数组
vector<int>k[100010];//邻接表
queue<int>q;//反正最后等队列为空才结束遍历，所以用一次后队列一定是空的，放在全局节省空间
void solve(){
    int n;
    cin>>n;
    for (int i=1;i<=n;i++){
        int u,v;
        cin>>u>>v;
        k[u].push_back(v);
        k[v].push_back(u);//邻接表储存图G
    }
    int ans=2;//这里是优化，因为答案至少是2，所以先设成2
    for (int i=1;i<=n;i++){
        if (vis[i]==0){//没被访问过，是新的环
            vis[i]=1;//标记该节点
            int cnt=1;//该节点也算在节点数内，所以初始化为1
            q.push(i);
            while (q.size()){
                int l=q.front();
                q.pop();
                for (auto o:k[l]){
                    if (vis[o]==0){//环的新节点
                        cnt++;//节点数+1
                        q.push(o);
                        vis[o]=1;
                    }
                }
            }
            if (cnt%2==1){
                ans=3;
                break;
            }//如果点数是奇数，那么答案是3，但答案最多也是3，所以可以直接结束，节省运行时间
        }
    }
    cout<<ans<<endl;
    memset(k,0,sizeof(k));
    memset(vis,0,sizeof(vis));//初始化，防MLE
}
int main(){
    int t;
    cin>>t;
    while (t--){
        solve();
    }//T组数据
    return 0;
}

---

结语：

希望对大家学习OI有帮助！