社区讨论

find的两种写法

2022/09/24 22:02学术版参与者 13已保存回复 26

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

Rt，有一些困惑。

我惯用的是循环写法：

CPP

inline int find(int x){
	while(x!=f[x])
		x=f[x]=f[f[x]];
	return x;
}

然后我突然发现除了我以外全班都是这样写的：

CPP

int find(int x){
	return x==f[x]?x:(f[x]=find(f[x]));
}

我想了想，我的写法似乎每次只能将长度干掉一半，而其他人的写法是全部连到祖先上去，那不是理应第二种吊打第一种吗？可是我拍了上百组，都是第一种时间小于等于第二种？

为什么？

共 26 条回复，欢迎继续交流。

正在加载回复...