[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，思路没有变动。

code

CPP

#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;
}

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

文章操作

相关推荐

评论

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