错误数据:
3.in
5 5
2 5
5 5
5 5
4 1
3 5
3.out
3
2 1 4
2 2 5
2 3 5
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,idx,ans,dfn[500005],low[500005],hd[500005];
vector<int> ve[500005];
stack<int> st;
vector<int> bcc[500005];
bool cmp(int a,int b){return a > b;}
void tarjan(int now,int root){
dfn[now] = low[now] = ++idx;
if(now == root && !hd[now]) bcc[++ans].push_back(now);
st.push(now);
for(auto i : ve[now]){
if(!dfn[i]){
tarjan(i,root);
low[now] = min(low[now],low[i]);
if(low[i] >= dfn[now]){
ans++;
int p;
do{
p = st.top();
st.pop();
bcc[ans].push_back(p);
}while(p != i);
bcc[ans].push_back(now);
}
}else low[now] = min(low[now],dfn[i]);
}
}
signed main(){
cin >> n >> m;
for(int i = 1;i <= m;i++){
int u,v; cin >> u >> v;
if(u == v) continue;
ve[u].push_back(v);
hd[u] = k++;
ve[v].push_back(u);
hd[v] = k++;
}
for(int i = 1;i <= n;i++){
if(!dfn[i]) tarjan(i,i);
}
cout << ans << "\n";
for(int i = 1;i <= ans;i++){
cout << bcc[i].size() << " ";
for(auto j : bcc[i]) cout << j << " ";
cout << "\n";
}
return 0;
}