这个是点双模板代码,问一下28行为什么不能用vec[index].size()代替son,这不是等价的吗?望指正!悬赏关注
#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int> vec[500100], ans[500100];
int low[500100], dfn[500100], ti, sta[500100], top, tot;
void dfs(int index, int back) {
low[index] = dfn[index] = ++ti;
sta[++top] = index;
int son = 0;
for(int i=0; i<vec[index].size(); ++i) {
if(vec[index][i] == back) continue;
if(!dfn[vec[index][i]]) {
son++;
dfs(vec[index][i], index);
low[index] = min(low[index], low[vec[index][i]]);
if(low[vec[index][i]] >= dfn[index]) {
++tot;
while(sta[top+1]!=vec[index][i]) {
ans[tot].push_back(sta[top]);
top--;
}
ans[tot].push_back(index);
}
} else {
low[index] = min(low[index], dfn[vec[index][i]]);
}
}
if(back == 0 && son == 0) {
ans[++tot].push_back(index);
}
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> n >> m;
for(int i=1; i<=m; ++i) {
int u, v; cin >> u >> v;
vec[u].push_back(v); vec[v].push_back(u);
}
for(int i=1; i<=n; ++i) {
if(dfn[i]) continue;
top = 0;
dfs(i, 0);
}
cout << tot << endl;
for(int i=1; i<=tot; ++i) {
cout << ans[i].size() << " ";
for(int j=0; j<ans[i].size(); ++j) {
cout << ans[i][j] << " ";
}
cout << endl;
}
return 0;
}