刚刚学习点双,勿喷.
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,idx,top,vdcccnt,root,cut[N],cnt[N],vdcc[N],stk[N],dfn[N],low[N];
vector <int> G[N],ans[N];
void dfs(int x){
dfn[x]=low[x]=++idx;
stk[++top]=x;
if (x==root&&!G[x].size()){
vdcccnt++;
top--;
ans[vdcccnt].push_back(x);
return ;
}
int son=0;
for (int i=0;i<G[x].size();i++){
int y=G[x][i];
if (!dfn[y]){
dfs(y);
son++;
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x]){
if (x!=root||son>1) cut[x]=1;
vdcccnt++;
int tem;
do{
tem=stk[top--];
ans[vdcccnt].push_back(tem);
}while (tem!=x);//错误
stk[++top]=x;//错误
//while (tem!=y);//正确
//ans[vdcccnt].push_back(x);//正确
}
}
else low[x]=min(low[x],dfn[y]);
}
}
int main(){
scanf ("%d%d",&n,&m);
for (int i=1;i<=m;i++){
int u,v;
scanf ("%d%d",&u,&v);
if (u==v) continue;
G[u].push_back(v);
G[v].push_back(u);
}
for (int i=1;i<=n;i++)
if (!dfn[i]){
root=i;
dfs(i);
}
printf ("%d\n",vdcccnt);
for (int i=1;i<=vdcccnt;i++){
printf ("%d ",ans[i].size());
for (int j=0;j<ans[i].size();j++)
printf ("%d ",ans[i][j]);
puts("");
}
return 0;
}
注释处存疑,两种写法看起来差不多,但一种48分,一种100分{{|└(>o<)┘|}}?!