[P8346] 「Wdoi-6」最澄澈的空与海 题解

· · 题解

直接考虑是非常困难的，考虑找到一个薄弱环节。

发现度数为 1 的结点 u 只能匹配其所连的边 (u,v) 对应的结点 v。结点 v 被匹配后，其连边都没有用了，可以直接删去。这样一来，可能产生新的度数为 1 的结点。如此循环，最终剩下若干个连通块。这个过程可以使用类似拓扑排序的方式实现。

考察一个留下来的连通块，若其点数为 1 则原图存在孤立点，必然无解。否则，其所有节点必然满足度数 \ge 2，于是必然存在一个大小 \ge 2 的环。

证明：连通，其必然能够取出一颗生成树，考虑树上任意一个度数为 1 的叶子，其另一条连边一定与这颗生成树上的边构成一个大小 \ge 2 的环。

二分图，得到的环是偶环，对环上的边进行黑白染色，可以得到两种方案：用黑边匹配或用白边匹配。

所以如果有剩余连通块，即删边过程中有点没有被匹配，要么无解要么多解。

时间复杂度：\mathcal{O}(n+m)。

2025.11.19 upd：修改了代码使其通过 hack，思路没有变动。

::::info[code]

#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long ll;
const ll maxn=2000007,p=998244353,B=14;
ll n,m,deg[maxn],vis[maxn],q[maxn],h,t;
vector<ll> edge[maxn];
void bfs(void){
    h=0,t=1;
    for(int i=1;i<=2*n;i++)if(deg[i]==1) q[++h]=i;
    for(ll u;h>=t;){
        u=q[t],t++;
        for(auto v:edge[u])if(!vis[v]){
            vis[v]=vis[u]=1;
            for(auto w:edge[v])if(!vis[w]){
                deg[w]--;
                if(deg[w]==1) q[++h]=w;
            }
        }
    }
}
string solve(void){
    bfs();
    for(int i=1;i<=2*n;i++)if(!vis[i]) return "Merry";
    return "Renko";
}
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    ll T=1; cin>>T;
    for(;T--;){
        for(int i=1;i<=2*n;i++) deg[i]=vis[i]=0,edge[i].clear();
        cin>>n>>m;
        for(int i=1,u,v;i<=m;i++){
            cin>>u>>v,edge[u].pb(v+n),edge[v+n].pb(u);
            deg[u]++,deg[v+n]++;
        }
        cout<<solve()<<"\n";
    }
    return 0;
}

::::