社区讨论
感觉是相同的写法但是有锅,悬 2 关
P8435【模板】点双连通分量参与者 2已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @lo1qsuyz
- 此快照首次捕获于
- 2023/10/23 01:28 2 年前
- 此快照最后确认于
- 2023/11/03 02:07 2 年前
这是 AC 代码:
CPP#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=5e5+5;
vector<int> e[N];
int dfn[N],low[N],cnt;
stack<int> s;
int sum;
vector<int> vdcc[N];
void tarjan(int u){
s.push(u);
dfn[u]=low[u]=++cnt;
for(int i=0;i<e[u].size();i++){
int v=e[u][i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
if(dfn[u]<=low[v]){
sum++;
s.push(u);
while(s.top()!=v){
vdcc[sum].push_back(s.top());
s.pop();
}
vdcc[sum].push_back(s.top());
s.pop();
}
}
else low[u]=min(low[u],dfn[v]);
}
if(!e[u].size()) vdcc[++sum].push_back(u);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
if(a!=b) e[a].push_back(b),e[b].push_back(a);
}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
printf("%d\n",sum);
for(int i=1;i<=sum;i++){
printf("%d ",vdcc[i].size());
for(int j=0;j<vdcc[i].size();j++){
printf("%d ",vdcc[i][j]);
}
puts("");
}
return 0;
}
如果我中间弹栈的时候改成:
CPP sum++;
while(s.top()!=u){
vdcc[sum].push_back(s.top());
s.pop();
}
vdcc[sum].push_back(s.top());
s.pop();
样例#4 就有问题。
感谢 Dalao!
回复
共 4 条回复,欢迎继续交流。
正在加载回复...