蒟蒻求助,悬关
查看原帖
蒟蒻求助,悬关
931707
017_007楼主2023/8/2 17:31

就是在dfs中,一个小细节的疑惑

这是代码。

#include<bits/stdc++.h>
#include<vector>
#define reg register
using namespace std;
inline int read() {
	int x=0,f=1;char s=getchar();
	while (s>'9'||s<'0') {
		if (s=='-') f=-f;
		s=getchar();
	}
	while (s>='0'&&s<='9') {
		x=(x<<3)+(x<<1)+(s-'0');
		s=getchar();
	}
	return x*f;
}
const int N = 2e4+10;
const int M = 1e5+10;
int n,m,u,v,first[N],cnt,dfn[N],low[N],fa[N],sons[N],sonmax[N],now;
vector<int>ans;
bool d[N],R[N];
struct edge{
	int to,nxt;
}edges[M*2];
void add(int u,int v) {
	edges[++cnt].to=v;
	edges[cnt].nxt=first[u];
	first[u]=cnt;
}
void dfs(int root) {
	dfn[root]=low[root]=++now;
	d[root]=true;
	for (reg int t=first[root];t;t=edges[t].nxt) {
		int h=edges[t].to;
		if (d[h]) low[root]=min(low[root],dfn[h]);
		else dfs(h),sons[root]++,low[root]=min(low[root],low[h]),fa[h]=root,d[h]=true,sonmax[root]=max(sonmax[root],low[h]);
	}
}
int main(){
	n=read();m=read();
	for (reg int i=1;i<=m;++i) u=read(),v=read(),
		add(u,v),add(v,u);
	for (reg int i=1;i<=n;++i) if (!dfn[i]) R[i]=true,dfs(i);
	for (reg int i=1;i<=n;++i) 
		if (R[i]) {
			if (sons[i]>1) ans.push_back(i);
		}
		else if (sonmax[i]>=dfn[i]) ans.push_back(i);
	printf("%d\n",ans.size());
	for (reg int i=0;i<ans.size();++i) printf("%d ",ans[i]);
	return 0;
}

在dfs中有一段,

if (dfs[h]) 
	low[root]=min(low[root],dfn[h]);

但是这段改成low[root]=min(low[root],low[h])的话就只有24分。一直有疑惑,希望有大佬帮忙解答,感激QAQ。

2023/8/2 17:31
加载中...