题解：P9923 [POI 2023/2024 R1] Przyciski

xlaser · 2026-04-27 14:28:06 · 题解

对于一个按钮 (x,y) 将 x 与 y+n 建边，问题转化成：在这张图上选一个子图，使得每个点度数的奇偶性相同。

首先如果有环，那么把环选上，所有点的度数都是偶数，满足条件，这里直接用 DFS 判环就可以了。

否则没有环，这个图就是一个森林。叶子节点只能向上连 1 条边，所以所有点的度数一定都是奇数。

于是对于每棵树，我们从叶子往上贪心选：对于一个点，如果有儿子的度数是偶数，就把这个点和这个儿子的边选上。

如果所有点都选完了之后还是有度数为偶数的点，就直接无解。

:::success[代码]

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

struct vw{
    int v,w;
};

int n,m;
vector<vw> edge[200010];
bool vis[200010];
bool vis2[200010];
vw f[200010];
vector<int> ans;

void dfs1(int p,int fa){
    vis[p]=true;
    for(vw v:edge[p]){
        if(v.v==fa){
            continue;
        }
        if(vis[v.v]){
            cout<<"TAK\n";
            ans.push_back(v.w);
            int x=p;
            while(x!=v.v){
                ans.push_back(f[x].w);
                x=f[x].v;
            }
            cout<<ans.size()<<'\n';
            for(int x:ans){
                cout<<x<<' ';
            }
            exit(0);
        }
        f[v.v]={p,v.w};
        dfs1(v.v,p);
    }
}

void dfs2(int p,int fa){
    vis2[p]=true;
    for(vw v:edge[p]){
        if(v.v==fa){
            continue;
        }
        dfs2(v.v,p);
        if(!vis[v.v]){
            ans.push_back(v.w);
            vis[v.v]=!vis[v.v];
            vis[p]=!vis[p];
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        edge[x].push_back({y+n,i});
        edge[y+n].push_back({x,i});
    }
    for(int i=1;i<=2*n;i++){
        if(!vis[i]){
            dfs1(i,0);
        }
    }
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=2*n;i++){
        if(!vis2[i]){
            dfs2(i,0);
        }
    }
    for(int i=1;i<=2*n;i++){
        if(!vis[i]){
            cout<<"NIE";
            return 0;
        }
    }
    cout<<"TAK\n";
    cout<<ans.size()<<'\n';
    for(int x:ans){
        cout<<x<<' ';
    }
    return 0;
}

:::