【模板】边双

这里介绍一种与众不同的写法。

前置知识：强联通分量

回忆强联通分量的算法过程，我们利用有向图的 dfn 树将图上的所有边分成四种：树边、前向边、后向边和横向边。

其中在原有树边的基础上，前向边不发挥作用，后向边一定发挥作用，横向边可能发挥作用，这个过程中我们维护了一个栈，用这个栈来确定一条边是否发挥作用（只有终点在栈里的边才会发挥作用）。

我们发现边双和强联通分量是类似的，所以可以将求强联通分量的算法拓展到无向图上，得到一个不需要求桥的边双算法。

首先一个重要的性质，在无向图除了树边就只有后向边，证明这里略过。

那么也就说明我们可以省去维护一个点是否在栈内的过程，栈内依然维护当前点的所有祖先点所属的边双中遍历过的所有点。

此时因为所有边都是后向边，即所有非树边都指向自己的祖先，可以直接转移更新 low。

这样就能做到甚至比普通的求强联通分量更加简单，但要注意一点，因为求的是无向图的边双，我们必须要将从父亲处过来的那条边（即树边）无视，可以直接像正常做 dfs 时那样将父亲特判掉，但因为可能出现重边，最好的办法是利用无向图相反边在链式前向星中相邻的特点直接得到需要特判掉的边的编号，如果没有重边则可以直接记录父亲编号。

你谷例题：P8436 【模板】边双连通分量。

代码比先求桥再分边双简单得多（老莽の代码头略大）。

#include<bits/stdc++.h>

using namespace std;

#define Reimu inline void // 灵梦赛高
#define Marisa inline int // 魔理沙赛高
#define Sanae inline bool // 早苗赛高
#define Reisen inline LL  // 铃仙赛高

typedef long long LL;
typedef unsigned long long ULL;
typedef __int128 Suika;

inline ostream &operator<<(ostream &cout, Suika x) {
	static const LL LIM = 1e18;
	return x < LIM ? cout << LL(x) : cout << LL(x / LIM) << setw(18) << setfill('0') << LL(x % LIM);
}

typedef pair<int, int> Pii;
typedef tuple<int, int, int> Tiii;
#define fi first
#define se second

#define all(vec) vec.begin(), vec.end()
#define TY(type) const type&

template<typename Ty>
Reimu clear(Ty &x) { Ty().swap(x); }

const int N = 500010, M = 2000010;

struct Edge { int y, nx; } E[M << 1];

int n, m, eCnt, tot, cnt, top;
int lnk[N], dfn[N], low[N], stk[N];
vector<int> cc[N];

Reimu addE(int x, int y) { E[eCnt] = {y, lnk[x]}; lnk[x] = eCnt++; }

Reimu Tar(int x, int fe) {
	dfn[x] = low[x] = ++tot;
	stk[++top] = x;
	for (int e = lnk[x], y; ~e; e = E[e].nx) if (e ^ fe) {
		if (dfn[y = E[e].y]) low[x] = min(low[x], dfn[y]);
		else Tar(y, e ^ 1), low[x] = min(low[x], low[y]);
	}
	if (low[x] < dfn[x]) return;
	++cnt; do cc[cnt].emplace_back(stk[top]); while (stk[top--] ^ x);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	cin >> n >> m;
	memset(lnk + 1, -1, n << 2);
	for (int i = 1, x, y; i <= m; ++i) cin >> x >> y, addE(x, y), addE(y, x);
	for (int i = 1; i <= n; ++i) if (!dfn[i]) Tar(i, -1);
	cout << cnt << '\n';
	for (int i = 1; i <= cnt; ++i) {
		cout << cc[i].size() << ' ';
		for (int x: cc[i]) cout << x << ' ';
		cout << '\n';
	}
	return 0;
}