题解

关键结论

• “无论怎样的 2-列表都能找到合法 2-染色” ⇔ 图是 2-可列染色图（2-choosable）。著名的 Erdős–Rubin–Taylor 定理给出了判定方法：把图反复删除度数 ≤ 1 的顶点，得到的核心若为空或每个块都属于以下三类之一，则图 2-choosable：
  1. 单条边（K₂）；
  2. 偶环；
  3. 两个 3 度顶点通过三条互不相交的路径相连，并且任意两条路径形成的环都是偶环（即所谓的 “θ 图”，三条臂的长度都同奇偶）。
• 因此整体做法：先剥离所有树枝，剩余部分（核心）必须是上述形式。若核心中存在奇环或出现度数 ≥ 4 的点，说明一定能构造出 2 个颜色集合让 pupil 失败。

判定流程

1. 剥离叶子：用队列不断删除度数 ≤ 1 的节点，得到核心。核心里的点都属于某个块。
2. 重建与二分性检查：仅保留核心的边，若核心不是二分图，则存在奇环必然失败。
3. 度数检查：核心中出现度数 > 3 的顶点直接判定失败。
4. θ 图校验：对每个度数等于 3 的连通块执行一次 DFS，统计：
   • c3：块内度 ≥ 3 的节点数量，若超过 2，则不可能是 θ 图；
   • cg1：用于记录三条臂之间的长度奇偶关系，一旦出现超过一个“奇长度臂”或多个回边破坏偶性，也应判定失败。 DFS 的过程同时沿着臂向外延伸，把度数 3 的节点视作根，逐层剥离直到所有高阶节点都处理完。若整个块满足 c3 ≤ 2 且 cg1 ≤ 1，则符合 θ 图的结构与奇偶要求。
5. 若所有块都通过上述检查，则整张图 2-choosable，输出 YES，否则输出 NO。

复杂度

• 剥离叶子与重新建图均为 O(n + m)；
• 每条边、每个点在 DFS 中只访问一次，总复杂度仍为 O(n + m)，可以承受 n,m ≤ 10^4 的数据范围。

参考实现

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
const int M=2e4+10;

int T;
int n,m;
pair<int,int> e[M];
vector<int> g[N];
int deg[N];
bool vis[N];
queue<int> q;
int col[N];
bool flag;
int d[N];
int c3,cg1;

void dfs1(int u,int c) {
    col[u]=c;
    for(int v:g[u]) {
        if(col[v]) {
            if(col[v]==c) flag=0;
            continue;
        }
        dfs1(v,3-c);
    }
}

void dfs2(int u,int fa=0) {
    vis[u]=1;
    c3+=g[u].size()>=3;
    for(int v:g[u]) {
        if(v==fa) continue;
        if(vis[v] && g[v].size()>3) cg1+=2;
        if(vis[v]) continue;
        d[v]=d[u]+1;
        if(g[v].size()>=3) {
            if(d[u]%2==0) cg1+=2;
            else if(d[u]>1) cg1++;
            deg[v]--;
            if(!deg[v]) dfs2(v,u);
        }
        else dfs2(v,u);
    }
}

bool solve() {
    for(int i=1;i<=n;i++) g[i].clear(),deg[i]=0,vis[i]=0;
    while(!q.empty()) q.pop();
    for(int i=1;i<=m;i++) {
        int u=e[i].first,v=e[i].second;
        g[u].push_back(v),g[v].push_back(u);
        deg[u]++,deg[v]++;
    }
    for(int i=1;i<=n;i++) if(deg[i]<=1) q.push(i);
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        vis[u]=1;
        for(int v:g[u]) {
            deg[v]--;
            if(deg[v]==1) q.push(v);
        }
    }
    for(int i=1;i<=n;i++) g[i].clear(),deg[i]=0,d[i]=0,col[i]=0;
    for(int i=1;i<=m;i++) {
        int u=e[i].first,v=e[i].second;
        if(vis[u] || vis[v]) continue;
        g[u].push_back(v),g[v].push_back(u);
        deg[u]++,deg[v]++;
    }
    for(int i=1;i<=n;i++) {
        if(col[i]) continue;
        flag=1;
        dfs1(i,1);
        if(!flag) return 0;
    }
    for(int i=1;i<=n;i++) {
        if(vis[i]) continue;
        if(deg[i]>3) return 0;
        if(deg[i]!=3) continue;
        c3=cg1=0;
        dfs2(i);
        if(c3>2 || cg1>1) return 0;
    }
    return 1;

}

int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++) {
            int u,v;
            scanf("%d%d",&u,&v);
            e[i]={u,v};
        }
        if(solve()) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}