并查集的板子题,但我想来点不一样的
解题思路
当节点 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);