CNS_5t0_0r2 @ 2023-11-16 10:19:41
https://www.luogu.com.cn/record/135330566
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 9,M = 2e6 + 9;
struct egde{
int to,nex;
} e[M << 1];
int ecnt,head[N];
void addegde(int u,int v){
ecnt++;
e[ecnt] = (egde){v,head[u]};
head[u] = ecnt;
}
int n,m,x,y;
int id,cnt,dfn[N],low[N];//id表示DFS序
vector<int> ans[N];//第i个连通分量的个点
stack<int>s;
void dfs(int cur,int father){//cur表示当前顶点,father表示其在生成树上的父节点
id++;
dfn[cur] = id;
low[cur] = id;//当前顶点一定能回到自己。
s.push(cur);
for(int i = head[cur];i;i = e[i].nex){
int v = e[i].to;
if(!dfn[v]){//如果这个顶点未被遍历到,遍历它
dfs(v,cur);
low[cur] = min(low[cur],low[v]);
//更新当前顶点能遍历到的最早dfn
}
else if(v != father)//否则如果顶点v被遍历过,并且不是cur的父节点,说明v是cur的非父祖先,因此可以不经过父节点到达它,更新当前节点能到的最小点的dfn
low[cur] = min(low[cur],dfn[v]);
}
if(low[cur] == dfn[cur]){
int v;
cnt++;
do{
v = s.top();s.pop();
ans[cnt].push_back(v);
}while(v != cur);
}
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1;i <= m;i++){
scanf("%d%d", &x, &y);
addegde(x,y);
addegde(y,x);
}
for(int i = 1;i <= n;i++)
if(!dfn[i])
dfs(i,0);
printf("%d\n",cnt);
for(int i = 1;i <= cnt;i++){
int siz = ans[i].size();
printf("%d ",siz);
for(int j = 0;j < siz;j++)
printf("%d ",ans[i][j]);
printf("\n");
}
return 0;
}
by Genius_Star @ 2024-01-15 21:47:26
@5t0_0r2 可能有重边