五下暑假/六上笔记

· · 个人记录

五下暑假部分

普及B组2班

2023-7-12比赛题解

2023-7-12比赛题解（温暖版）

团队题单

六上部分

1、并查集

主体代码（初版）：

int find(int i)
{
    while(i != NULL)
        i = fa[i];
    return i;
}

但是这样如果遇上一左一右这么摆下来的二叉树，那么时间复杂度则会非常巨大。于是我们的输入可以进行调整，由cin >> a >> b; fa[b] = a改变成cin >> a >> b; if(find(a) != find(b)) fa[find(b)] = find(a)

此代码就是union（合并） 因为如果当输入要将两个点连起来时，如果直接连，程序会显得异常杂乱，我们便可以将两个节点的父节点给连接起来，会更加简便。

我们还可以将之前的函数进行改进：

int find(int i)
{
    return i == fa[i] ? i : fa[i] = find(fa[i]);
}

同样是刚才那个原理，我们在寻找一个结点的最终父节点时，不用先找到它的父节点，而是直接把它赋值为它父节点的最终父节点，最后加一个特判，如果它的父节点就是自己，则直接返回自己的值。

题目一般本质上就是求两个节点是不是拥有同样的父节点，用上这一句就可以了：

if(find(u) == find(v))