P11031 『DABOI Round 1』Completely Unrelated 题解

· · 题解

Solution

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

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

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

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

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

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

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

复杂度分析

综上所述，总复杂度为 \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();
}