#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], timestamp, top; int n, m; int bcc_cnt; vector bcc[N]; //边双中有哪些点 void tarjan(int u, int from) { dfn[u] = low[u] = ++timestamp; stk[++top] = u; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (!dfn[j]) { tarjan(j, i); // j:点,i:哪条边 low[u] = min(low[u], low[j]); } else if (i != (from ^ 1)) low[u] = min(low[u], dfn[j]); } if (dfn[u] == low[u]) { ++bcc_cnt; //边双数量+1 int x; do { x = stk[top--]; bcc[bcc_cnt].push_back(x); // 记录边双中有哪些点 } while (x != u); } } int main() { //文件输入输出 #ifndef ONLINE_JUDGE freopen("P8436.in", "r", stdin); #endif scanf("%d %d", &n, &m); memset(h, -1, sizeof h); for (int i = 1; i <= m; i++) { int a, b; scanf("%d %d", &a, &b); if (a != b) add(a, b), add(b, a); } for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, -1); //输出边双个数 printf("%d\n", bcc_cnt); for (int i = 1; i <= bcc_cnt; i++) { printf("%d ", bcc[i].size()); for (int j : bcc[i]) printf("%d ", j); printf("\n"); } return 0; }