关于第一次 dfs 的疑问
查看原帖
关于第一次 dfs 的疑问
730828
UMS2楼主2024/2/27 10:01

几个月前我是这么写的,能过R118322717。

void dfs(int d,int f,int u){
	dep[u]=d;
	fa[u]=f;
	size[u]=1;
    int soc=-1;
    
	for(int i=h[u];i;i=e[i].u){
		int v=e[i].v;
		if(v!=f){
			dfs(d+1,u,v);
			size[u]+=size[v];
			if(size[v]>soc){
			    son[u]=v;
			    soc=size[v];
			}
		}
	}
}

最近复习,想优化一下,写成这样。

void dfs(int u){
	dep[u]=dep[fa[u]]+1;
	size[u]=1;
	
	for(int i=h[u];i;i=e[i].u){
		int v=e[i].v;
		if(v!=fa[u]){
		    fa[v]=u;
			dfs(v);
			size[u]+=size[v];
			if(size[v]>son[u])son[u]=v;
		}
	}
}

却直接 T 了 3 个点,R148486659。

测试了一下,发现是把 soc 删掉之后 T 的,即使只是把 soc 放在 for() 里都会慢将近 200ms,R148486941。

这是为啥,访问数组比访问变量更慢吗?

2024/2/27 10:01
加载中...