ID_9324 亲戚

并查集的板子题,但我想来点不一样的

解题思路

当节点 u 和节点 v 是亲戚时,我们在节点 u 和节点 v 之间建一条无向边

然后遍历每一个节点,对于第 i 个节点

1.节点 i 没有被遍历过,那么我们就 dfs 之,将所有直接或间接连接节点 i 的节点标记成同一个颜色

2.节点 i 被遍历过,跳过

时间复杂度 O(n) ,而且常数极小,在大数据下效率可能比并查集还高(信友队的数据还是水了)!

代码

dfs每个节点

void dfs(int now, int x)
{
	color[now] = x;
	b[now] = 1;
	for (int i = 0; i < e[now].size(); i++)
		if (!b[e[now][i]])
			dfs(e[now][i], x);
}

遍历每个节点

for (int i = 1; i <= n; i++)
	if (!b[i])
		dfs(i, ++num);
2 个赞