这东西显然比广义串并联图和 cluster 上的 DDP 不知道简单到哪里去了 /fn
首先回顾一下几个比较基础的定义：
- 边连通度：两个点之间的边连通度就是它们之间的最小割大小，即，最小的 \(e\) 使得存在一种割掉 \(e\) 条边的方案使得这两点不连通。
- 点连通度：类比边连通度，两点之间的点连通度是最小的 \(x\) 使得存在一种删掉 \(x\) 个点的方案使得这两点不连通。
- \(k\) 边连通分量：极大的点集使得点集中任意两点之间的边连通度都 \(\ge k\)，由于边连通度存在传递性（即，如果 \(x,y\) 之间边连通度 \(\ge k\)，\(y,z\) 之间边连通度 \(\ge k\)，那么 \(x,z\) 之间边连通度 \(\ge k\)），因此 \(k\) 边连通分量是良定义的。
- \(k\) 点连通分量：极大的点集使得点集中任意两点之间的点连通度都 \(\ge k\)，由于 \(k\ge 3\) 时点连通度不存在传递性，所以一般我们只关心 \(k=2\) 时的 \(k\) 点连通分量。
\(k=1\) 是普及组算法，\(k=2\) 是提高组算法，因此这里我们着重讨论 \(k=3\) 的情况，即无向图边三连通分量的求解。求解 \(k\) 边连通分量有一个普适的做法就是建出最小割树，根据最小割树的性质，两点在同一 \(k\) 边连通分量中当且仅当它们路径上边权最小值 \(\ge k\)，但是该做法不在我们今天讨论的范围内。
显然，两点不在一个边三连通分量中当且仅当存在两条边 \(e_1,e_2\) 使得割掉 \(e_1,e_2\) 后两点不在同一连通块中。朴素判断需要三方的时间，因此需要一些优化。首先考虑一个引理：
引理：对于一张无向图，求出它的一棵 DFS 树，对于第 \(i\) 条非树边负权 \(2^{i-1}\)，树边的权值是覆盖它的非树边权值的异或和，那么对于一个边集而言，割掉该边集后图不连通当且仅当该边集的权值组成的集合线性相关。
当然，这里 \(2^{i-1}\) 的唯一的用处就是构造线性无关集，在实现时换成 xor hash 也大概率是等效的。
首先我们对每个边双分开来考虑，显然不在同一边双中的点也肯定不在同一边三中。我们讨论割掉的两条边的关系：
- 两条非树边，由于树边已经使整张图连通了，所以此时图必然连通。
- 一条树边和一条非树边，显然这条非树边必须是唯一一条覆盖这条树边的非树边，这时候我们在这条树边两个端点中打一个子树异或标记将两部分区分开来即可。
- 两条树边，显然这两条非树边的权值必须相同，由于两条树边在同一点双中，因此必然有非树边跨过这两条树边，这样割掉这两条树边后，两边的两个连通块依然连通，中间的连通块就被孤立开来了。这可以通过在两条非树边中深度较深的点处打同一个子树异或标记解决——这样中间的每个点恰好被异或一次，两边的连通块恰好被异或零次。朴素地做要对 \(O(n^2)\) 个树边对进行这个操作，但是仔细一想可以发现，类比虚树，如果我们将所有权值相同的树边按两个端点中较深者的 DFS 序从小到大排序，那么如果我们只对 DFS 序序列上相邻两者进行异或操作，那么和对全部 \(O(n^2)\) 个树边对进行操作其实是等效的，这样就只用进行 \(O(n)\) 次打标记操作。
下面给出模板题的代码：
const int MAXN=5e5;
int n,m;
struct graph{
int hd[MAXN+5],to[MAXN*2+5],nxt[MAXN*2+5],ec=1;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
}G,T;
u64 xorshift(){
static u64 seed=1064;
seed^=seed<<13;seed^=seed>>17;seed^=seed<<7;
return seed;
}
int dfn[MAXN+5],low[MAXN+5],tim;u64 mark[MAXN+5],hsh[MAXN+5],typ[MAXN+5];
vector<pii>te;vector<int>pt;
void tarjan(int x,int lste){
pt.pb(x);dfn[x]=low[x]=++tim;
for(int e=G.hd[x];e;e=G.nxt[e])if(e!=(lste^1)){
int y=G.to[e];
if(!dfn[y]){
tarjan(y,e);chkmin(low[x],low[y]);
T.adde(x,y);T.adde(y,x);
if(low[y]>dfn[x])hsh[y]^=xorshift();
}else{
chkmin(low[x],dfn[y]);
if(dfn[y]>dfn[x])te.pb(mp(x,y));
}
}
}
void dfspush1(int x,int f){
for(int e=T.hd[x];e;e=T.nxt[e]){
int y=T.to[e];if(y==f)continue;
dfspush1(y,x);mark[x]^=mark[y];
}
}
void dfspush2(int x,int f){
for(int e=T.hd[x];e;e=T.nxt[e]){
int y=T.to[e];if(y==f)continue;
hsh[y]^=hsh[x];dfspush2(y,x);
}
}
map<u64,vector<int> >cmp;
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<=m;i++)scanf("%d%d",&u,&v),G.adde(u,v),G.adde(v,u);
for(int i=1;i<=n;i++)if(!dfn[i]){
pt.clear();te.clear();tarjan(i,0);
// for(pii p:te)printf("%d %d\n",p.fi,p.se);
map<u64,vector<int> >hss;
for(pii p:te){
u64 hs=xorshift();hss[hs].pb(-1);
mark[p.fi]^=hs;mark[p.se]^=hs;
}dfspush1(i,0);
for(int x:pt)if(x!=i)hss[mark[x]].pb(x);
// for(int x:pt)printf("mark[%d]=%llu\n",x,mark[x]);
for(auto ttt:hss){
vector<int>vec=ttt.se;bool flg=0;
for(int x:vec)flg|=(x==-1);
if(flg){
for(int x:vec)if(x!=-1)/* printf("! %d\n",x), */hsh[x]^=xorshift();
}else{
sort(vec.begin(),vec.end(),[&](int x,int y){return dfn[x]<dfn[y];});
for(int j=1;j<vec.size();j++){
u64 hs=xorshift();
// printf("!! %d %d\n",vec[j-1],vec[j]);
hsh[vec[j-1]]^=hs;hsh[vec[j]]^=hs;
}
}
}hsh[i]^=xorshift();dfspush2(i,0);
}
for(int i=1;i<=n;i++)cmp[hsh[i]].pb(i);
vector<vector<int> >res;
for(auto ttt:cmp)res.pb(ttt.se);
for(int i=0;i<res.size();i++)sort(res[i].begin(),res[i].end());
vector<int>ord(res.size());
for(int i=0;i<res.size();i++)ord[i]=i;
sort(ord.begin(),ord.end(),[&](int x,int y){return res[x][0]<res[y][0];});
printf("%d\n",res.size());
for(int id:ord){for(auto x:res[id])printf("%d ",x);printf("\n");}
return 0;
}