P14779 [COCI 2025/2026 #3] 宴会 / Domjenak Solution

Ptll · 2026-05-08 11:20:35 · 题解

题解

首先考虑确定出互相对应的两个点，这里可以考虑拓扑。

考虑令需要更新的点令为 0，反之则为 1，这个图就是 01 间隔的一张图。

由于规则四以及唯一性，我们可以考虑对于所有为 1 的点向它所连的点进行拓扑，这样当一个为 0 的点只剩下一条连边时就是和它配对的点。

我们发现，每个图是可以拆成一条条链，对于每条链都是 0/1 间隔的，但转换成图时，某一些点与它的朋友的颜色会相同。

这又发现对于答案肯定是同伴到朋友再到同伴以此类推。

这提示我们可以让同伴的朋友向当前点建边，这样就形成了一个 DAG，可以拓扑了。

在拓扑过程中考虑对连向的点进行转移（在图中就是一个由下到上的运动），最后输出路径即可。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <queue>
#ifdef _WIN32
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#else
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef __int128 i128;
namespace io {
    using namespace std;
    template <typename T> void debug (T x) {
        cerr<<x<<'\n';
    }
    template <typename T> void debuglen (T x) {
        cerr<<x<<' ';
    }
    template <typename T,typename...Args> void debug (T x,Args...args) {
        cerr<<x<<' ';
        debug(args...);
    }
    template <typename T> void debug (T*lt,T*rt) {
        ll len=rt-lt;
        for (ll i=0;i<len;i++) {
            debuglen(*(lt+i));
        }
        cerr<<'\n';
    }
    inline ll read () {
        char x=getchar();
        ll ans=0,f=1;
        while (x<'0'||x>'9') {
            if (x=='-') {
                f=-1;
            }
            x=getchar();
        }
        while (x>='0'&&x<='9') {
            ans=(ans<<1)+(ans<<3);
            ans+=(x^'0');
            x=getchar();
        }
        return ans*f;
    }
    void print (ll x) {
        if (x<0) {
            x=-x;
            putchar('-');
        }
        if (x>=10) {
            print(x/10);
        }
        putchar(x%10+'0');
    }
}
using namespace io;
const ll N=1e6+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
ll n,m,a[N],in[N],du[N],f[N],pos[N];
bool vis[N];
vector<ll> v[N],g[N];
queue<pll> q;
void dfs (ll x) {
    if (!x) {
        return ;
    }
    dfs(pos[x]);
    print(a[x]);
    putchar(' ');
    print(x);
    putchar(' ');
}
inline void solve () {
    n=read(),m=read();
    for (ll i=1;i<=m;i++) {
        ll ul=read(),vl=read();
        v[ul].push_back(vl);
        v[vl].push_back(ul);
    }
    for (ll i=1;i<=(n<<1);i++) {
        if (v[i].size()==1) {
            q.push({i,0});
        }
    }
    while (!q.empty()) {
        pll dl=q.front();
        q.pop();
        ll d=dl.first,col=dl.second;
        vis[d]=1;
        if (!col) {
            for (auto it : v[d]) {
                if (!vis[it]) {
                    a[it]=d;
                    a[d]=it;
                    q.push({it,1});
                    break;
                }
            }
        }
        else {
            for (auto it : v[d]) {
                if (a[d]==it) {
                    continue;
                }
                in[it]++;
                if (in[it]==v[it].size()-1) {
                    q.push({it,0});
                }
            }
        }
    }
    for (ll i=1;i<=(n<<1);i++) {
        for (auto it : v[a[i]]) {
            if (i==it) {
                continue;
            }
            g[it].push_back(i);
            du[i]++;
        }
    }
    for (ll i=1;i<=(n<<1);i++) {
        if (!du[i]) {
            q.push({i,0});
        }
    }
    ll ans=0;
    while (!q.empty()) {
        ll d=q.front().first;
        q.pop();
        f[d]=max(f[d],2ll);
        if (f[ans]<f[d]) {
            ans=d;
        }
        for (auto it : g[d]) {
            du[it]--;
            if (!du[it]) {
                q.push({it,0});
            }
            if (f[it]<f[d]+2) {
                f[it]=f[d]+2;
                pos[it]=d;
            }
        }
    }
    print(f[ans]);
    puts("");
    dfs(ans);
}
int main () {
    // freopen("domjenak.in","r",stdin);
    // freopen("domjenak.out","w",stdout);
    ll T=1;
    // T=read();
    while (T--) {
        solve();
    }
    return 0;
}