自动搬运

查看原文

来自洛谷，原作者为

	LKY928261 **

搬运于2025-08-24 23:03:38，当前版本为作者最后更新于2024-09-09 09:15:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

定义一些点和边“相对稳定”表示它们的相对位置不会发生变化，形式化地讲就是在固定住了其中任意一条边后，其余点和边的位置全部随之固定。

于是问题转化为判断整个图是否“相对稳定”。

因为边的“相对稳定”具有传递性，所以可以使用并查集维护。

当若干条边“相对稳定”时，它们的所有端点也是“相对稳定”的。所以我们可以同时维护一个并查集内的边的端点。

而当两个点“相对稳定”时，它们之间的边和它们也是“相对稳定”的。所以对于一些“相对稳定”的点，我们可以把它们之间没连的边全部连上。

那么根据以上结论，这题的思路也就一目了然了：

1. 对边维护并查集，对每个并查集维护其包含的所有边的所有端点构成的点集，初始每条边的点集即为其两个端点；
2. 去重后依次加入每条边，加边时枚举一遍点，判断是否能组成三元环（即三角形），如果能，则这三条边“相对稳定”，就将它们合并到一个并查集；
3. 进行合并操作时：
   1. 先枚举两个并查集的点集之间的边：
      • 若该边存在，那么当前并查集还需和该边对应的并查集合并，注意要等当前合并操作完成后再进行；
      • 若该边不存在，那么新建这条边，并把这条边加入加边队列中；
   2. 最后进行常规的并查集合并，然后处理前面 3-1-1 中需要处理的合并操作。

复杂度分析

• 一共 $\mathcal{O}(n^2)$ 条边，每条边 $\mathcal{O}(n)$ 枚举三元环——$\mathcal{O}(n^3)$；
• 合并时会枚举点集之间的连边，$\mathcal{O}(n^2)$ 条边，每条边只会在两端点所在并查集合并时被判断一次——$\mathcal{O}(n^2)$；
• 最多进行 $\mathcal{O}(n^2)$ 次并查集合并与查询操作——$\mathcal{O}(n^2\alpha(n))$。

综上所述，总复杂度为 $\mathcal{O}(n^3)$，足够通过此题。

Hack 数据

这里是我自己造的以及经过搜集整合得到的一些 hack 数据。

需要指出的是，基于合并三元环的拓扑排序的做法（也就是原 std 做法）是假的，因为这种做法无法处理由“相对稳定”的传递性产生的“虚边”。Hack 数据里的第 4 组就是针对这个造的。

Code

代码能通过现有数据和 hack，但是我也不敢保证细节上没有写挂，如果认为我的代码有问题的话欢迎指出。

#include<bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef int ll;
const ll _=205;
ll N,n,m,x,y,b[_*_],i,j;bool a[_][_];bitset<_>c[_*_];queue<ll>q;
inline ll p(ll x){return b[x]==x?x:b[x]=p(b[x]);}
inline void p2(ll x,ll y){
	x=p(x);y=p(y);if(x==y)return;
	vector<ll>u,v,w;
	for(ll i=1;i<=n;i++)if(c[x][i]^c[y][i]){if(c[x][i])u.eb(i);if(c[y][i])v.eb(i);}
	//↑当点在恰好一个点集中出现时才有必要枚举，
	//原因是如果在两个点集中都出现，那么它连出去的所有边都已经被连过了，
	//不加这个优化的话，复杂度可能会退化成 O(n^4)。
	for(ll i:u)for(ll j:v)if(i!=j){
		ll z=p(i*n-n+j);
		if(!a[i][j])a[i][j]=a[j][i]=1,b[z]=x,q.push(i*n-n+j);
		else w.eb(z);
	}
	c[x]|=c[y];b[y]=x;
	for(ll z:w)p2(x,z);
}
inline void P(){
	cin>>n>>m;memset(a,0,sizeof(a));
	for(i=0;i<m;i++)cin>>x>>y,a[x][y]=a[y][x]=1;
	if(n==1){cout<<"Yes\n";return;}
	if(n==2){cout<<(m?"Yes\n":"No\n");return;}
	for(i=1;i<n;i++)for(j=i+1;j<=n;j++){
		x=i*n-n+j;b[x]=b[j*n-n+i]=x;
		c[x]=0;c[x][i]=c[x][j]=1;
	}
	for(i=1;i<=n;i++){
		for(j=1;j<i;j++)if(a[i][j])q.push(i*n-n+j);
		while(q.size()){
			y=q.front();x=(y-1)/n+1;y=(y-1)%n+1;q.pop();
			for(j=1;j<i;j++)if(a[x][j]&&a[y][j])p2(x*n-n+y,x*n-n+j),p2(x*n-n+y,y*n-n+j);
		}
	}
	cout<<((ll)c[p(2)].count()==n?"Yes\n":"No\n");
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;while(N--)P();
}