第三个样例不仅少算了一个连通分量,甚至有一个连通分量的点输出0,真的找不到问题了求调
#include<bits/stdc++.h>
using namespace std;
const int N = 1000100;
int n,m;
int head[N],nextx[N],to[N],num;
int dfn[N],low[N],ins[N],s[N],tot,root,top;//s为栈储存当前的联通分量的元素,ins标记当前元素是否在栈内部 ,tot为dfs的顺序
int cnt;//为连通块的个数
vector<int> f[N * 2];//储存每一个前连通分量的信息
int sortt[N];
void add(int start,int end){
to[++num] = end;
nextx[num] = head[start];
head[start] = num;
}
void tarjan(int noww){
dfn[noww] = ++tot;
low[noww] = tot;//初始化low
s[++top] = noww;
ins[noww] = 1;
if(noww == root && head[noww] == 0){
f[++cnt].push_back(noww);//为根节点且没有边,那就放入新的强连通分量数组内
return;
}
for(int i = head[noww];i != 0;i = nextx[i]){
int son = to[i];
if(dfn[son] == 0){
tarjan(son);
low[noww] = min(low[noww],low[son]);
if(low[son] >= dfn[noww]){
cnt++;//当前点为割点,连通块数量加一
int z,topp = top;
do{
z = s[top--];
ins[z] = 0;//清除标记
f[cnt].push_back(z);
}while(z != son);
f[cnt].push_back(noww);
//对输出排序
for(int j = 0;j < topp;j++){
sortt[j] = f[cnt][j];
}
sort(sortt ,sortt + topp);
for(int j = 0;j < topp;j++){
f[cnt][j] = sortt[j];
}
}
}else if(ins[son] == 1){
low[noww] = min(low[noww],low[son]);
}
}
}
int main(){
cin>>n>>m;
int u,v;
for(int i = 1;i <= m;i++){
cin>>u>>v;
if(u == v){
continue;
}
add(u,v);
add(v,u);
}
for(int i = 1;i <= n;i++){
if(dfn[i] == 0){//若未被访问过
root = i;//以当前节点为树根进行dfs
tarjan(i);
}
}
cout<<cnt<<endl;
for(int i = 1;i <= cnt;i++){
cout<<f[i].size()<<" ";
for(int j = 0;j < f[i].size();j++){
cout<<f[i][j]<<" ";
}
cout<<endl;
}
return 0;
}