社区讨论

感觉是相同的写法但是有锅,悬 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 条回复,欢迎继续交流。

正在加载回复...