边三连通分量学习笔记

· · 休闲·娱乐

边三可以是一个结构也可以是一种 trick，所以会被塞到 trick 合集 里面。

在一张无向图上，如果两个点之间存在 3 条边不重复的路径，那么这两个点就在同一个边三连通分量里。

求边三连通分量总体考虑把不同连通分量两两区分开，如已知点集 A 和点集 B 之间的边不超过 2 条，那么就可以给 A 内所有的点打一个 xor hashing 用的随机标记，用于区分；最终每个点的 hash 值就代表了他所在的边三连通分量。

先求出一棵生成树，给每个非树边赋一个随机权值，并一同添加到这条非树边包含的路径上的边。考虑断开的边的情况：

  1. 一条树边：树边权值为 0
  2. 一条树边和一条非树边：树边权值恰好为任意一条非树边权值
  3. 两条树边：可以发现是两条树边的权值相同时，同时断开会导致中间的一部分分裂出去。

事实上，可以把上述结论总结为 k 条边线性相关时断开后图不连通。详细证明见 link。简单来说，每条边记录了自己所在的回路的集合，割边集合哈希值异或为 0 表示割边集合和回路集合的点积为 0。

写的时候写两个 xor hashing 用来记录点权和边权即可。

边三本身的结构很特殊，首先边三是边双的子结构，每个边双内部的边三缩起来之后会形成严格（每条边都在恰好一个环内）的仙人掌。

在处理切两条边图不连通的计数时，除了简单地通过边哈希值判定（哈希值相同即切割后不连通），可以发现切割仙人掌同一个环上的两条边会使图不连通，这提示边的哈希值对应了在仙人掌上的环的位置。

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ull = unsigned long long;
namespace Rand{
    ull cur = 19260817;
    ull getr(){
        cur ^= cur << 15;
        cur ^= cur >> 17;
        cur ^= cur << 7;
        return cur;
    }
}
const int N = 5e5 + 5;
int n, m;
vector<pair<int, int>> e[N];
vector<int> e2[N];
gp_hash_table<ull, bool> sedge;
gp_hash_table<ull, vector<int>> mp, mp2;
vector<vector<int>> ans;
ull mark[N], tag[N];
int dfsnum, dfn[N], rev[N];
void dfs(int u, int fae){
    rev[dfn[u] = ++dfsnum] = u;
    for (auto [v, eid] : e[u]){
        if (eid == fae) continue;
        if (!dfn[v]){
            e2[u].push_back(v);
            dfs(v, eid);
            mark[u] ^= mark[v];
        }else if (dfn[u] >= dfn[v]){
            ull eh = Rand::getr();
            mark[u] ^= eh;
            mark[v] ^= eh;
            sedge[eh] = 1;
        }
    }
}
void dfs2(int u){
    for (int v : e2[u]){
        tag[v] ^= tag[u];
        dfs2(v);
    }
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//  freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout); 
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        e[u].emplace_back(v, i);
        e[v].emplace_back(u, i);
    }
    sedge[0] = 1;
    vector<int> rt;
    for (int i = 1; i <= n; i++)
        if (!dfn[i]){
            rt.push_back(i);
            dfs(i, 0);
        }
    for (int i = 1; i <= n; i++){
        int j = rev[i];
        if (sedge.find(mark[j]) != sedge.end()) tag[j] ^= Rand::getr();
        mp[mark[j]].push_back(i);
    }
    for (auto [_, vec] : mp)
        if ((int)vec.size() > 1)
            for (int i = 1; i < (int)vec.size(); i++){
                ull eh = Rand::getr();
                tag[rev[vec[i - 1]]] ^= eh;
                tag[rev[vec[i]]] ^= eh;
            }
    for (int u : rt) dfs2(u);
    for (int i = 1; i <= n; i++) mp2[tag[i]].push_back(i);
    for (auto [_, vec] : mp2) ans.push_back(vec);
    sort(ans.begin(), ans.end(), [&](const vector<int> &vec1, const vector<int> &vec2){return vec1[0] < vec2[0];});
    cout << ans.size() << endl;
    for (vector<int> vec : ans){
        for (int x : vec) cout << x << ' ';
        cout << endl;
    }
    return 0;
}