题解：P6914 [ICPC2015 WF] Tours

· · 题解

切边等价

在一个边双连通图中，定义两条切边等价当且仅当在 G 的任何一个简单环中这两条边要么同时出现，要么同时不出现。

定义等价于在 G 中删去这两条边后 G 不连通，等价于在 G 的任意一棵生成树 T 中，假设 e_1，e_2 为树边，不存在任何一条非树边跨过其中一条边而不跨过另一条边。

求等价类时，考虑为每条非树边设置一个随机权值，定义树边的权值为所有跨过它的非树边的权值异或和，显然这是一个非确定性算法，但正确率很高，且确定性算法复杂度较高，所以该算法适用面更广。

对于树边，若权值为 0，则为割边，并可按权值划分等价类，权值计算可以通过树上差分完成。

ICPC2015 WF Tours

首先如果对于一个由多个简单环组成的环，若组成它的简单环均满足条件则它一定满足条件，我们就不用处理这种环，接下来考虑对于两个起点只出现一次的简单环 A，B，可以知道 A \oplus B 也必须要满足条件，将这三个环拆分成 A \cap B，A - A\cap B 和 B - A\cap B，可以证明 A，B 和 A \cap B 都是其中两个拆分的合并，接下来按此递归直到所有的边集无交，随后答案就是这些边集大小 \gcd 的因数，而两条边在同一边集的条件就是在所有的简单环内必须同时出现/不出现，刚好就是切边等价类。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define N 2005
vector<pair<int,int>> v[N];
int n,m,ans,tr[N],rk[N],vis[N],num[N],sam[N],use[N];
void dfs1(int x){
    vis[x]=1;
    for(auto [y,i]:v[x]){
        if(use[i]++)  continue;
        if(!vis[y])  {dfs1(y);continue;}
        tr[x]^=(rk[i]=num[i]=rand()),tr[y]^=num[i];
    }
}
void dfs2(int x){
    vis[x]=0;
    for(auto [y,i]:v[x]){
        if(!vis[y])  continue;
        dfs2(y),tr[x]^=(rk[i]=num[i]=tr[y]);
    }
}
int main(){
    srand(time(NULL)),scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y);
        v[x].emplace_back(y,i),v[y].emplace_back(x,i);
    }
    for(int i=1;i<=n;i++)  if(vis[i]==0)  dfs1(i);
    for(int i=1;i<=n;i++)  if(vis[i]==1)  dfs2(i);
    sort(rk+1,rk+m+1);int cnt=unique(rk+1,rk+m+1)-rk-1;
    for(int i=1;i<=m;i++)  sam[lower_bound(rk+1,rk+cnt+1,num[i])-rk]++;
    for(int i=1;i<=cnt;i++)  if(rk[i])  ans=gcd(ans,sam[i]);
    for(int i=1;i<=ans;i++)  if(ans%i==0)  printf("%d ",i);
}