#include using namespace std; const int N = 5e5 + 10, M = 4e6 + 10; int e[M], h[N], idx, w[M], ne[M]; void add(int a, int b, int c = 0) { e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++; } int dfn[N], low[N], stk[N], top, ts, root; int n, m; // 边双模板 int bcnt; vector bcc[N]; // 这里与有向图的强连通分量有区别,那个是id[N]+sz[N]静态数组实现,记录的是某个点在哪个强连通分量中, // 而这里,记录的是某个边双连通分量中有哪些节点,是捋着的顺序不同,实现方式不同,无法追求统一,否则就会在某种场景下造成使用双重循环使得代码TLE掉, // 不要问我是怎么知道的~ void tarjan(int u, int from) { dfn[u] = low[u] = ++ts; stk[++top] = u; // 边双连通分量模板,对比有向图强连通分量,只用栈记录数据,并没有用状态数组in_stk标识是否某节点在栈中 for (int i = h[u]; ~i; i = ne[i]) { int v = e[i]; if (!dfn[v]) { tarjan(v, i); // v:点,i:哪条边 low[u] = min(low[u], low[v]); } else if (i != (from ^ 1)) low[u] = min(low[u], dfn[v]); } if (dfn[u] == low[u]) { ++bcnt; // 边双数量+1 int x; do { x = stk[top--]; bcc[bcnt].push_back(x); // 记录边双中有哪些点 } while (x != u); } } int main() { memset(h, -1, sizeof h); scanf("%d %d", &n, &m); while (m--) { int a, b; scanf("%d %d", &a, &b); if (a != b) add(a, b), add(b, a); } for (root = 1; root <= n; root++) if (!dfn[root]) tarjan(root, -1); // 个数 printf("%d\n", bcnt); for (int i = 1; i <= bcnt; i++) { printf("%d ", bcc[i].size()); for (auto j : bcc[i]) printf("%d ", j); printf("\n"); } return 0; }