并查集基础一、概念及其介绍并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。并查集的思想是用一个数组表示了整片森林（parent），树的根节点唯一标识了一个集合，我们只要找到了某个元素的的树根，就能确定它在哪个集合里。二、适用说明并查集用在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这个过程看似并不复杂，但数据量极大，若用其他的数据结构来描述的话，往往在空间上过大，计算机无法承受，也无法在短时间内计算出结果，所以只能用并查集来处理。三、并查集的基本数据表示
并查集基础一、概念及其介绍并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。并查集的思想是用一个数组表示了整片森林（parent），树的根节点唯一标识了一个集合，我们只要找到了某个元素的的树根，就能确定它在哪个集合里。二、适用说明并查集用在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这个过程看似并不复杂，但数据量极大，若用其他的数据结构来描述的话，往往在空间上过大，计算机无法承受，也无法在短时间内计算出结果，所以只能用并查集来处理。三、并查集的基本数据表示
前言前几天看到并查集的题目，竟然只会最简单的并查集，看来带权并查集和扩展域并查集还要是好好写个笔记复习复习的。时间复杂度如果仅仅使用路径压缩的并查集，时间复杂度似乎并不是\(O(\alpha(n))\)，详情见这里。扩展域并查集yxc给出了一种简单易懂的理解扩展域并查集的方式：将并查集中的元素看成一个个条件，两个元素在一个集合中的意义是：如果有一个条件，那么整个集合中的条件都成立。我来形式化一点：并查集中的每一个元素都是一个语句\(p\)，每一个集合\(S\)都是一个命题：\(如果p(p\inS)，那么q(q\inS,q\not=p)。\)这样就十分容易理解了。例如：P2024[NOI2001
前言前几天看到并查集的题目，竟然只会最简单的并查集，看来带权并查集和扩展域并查集还要是好好写个笔记复习复习的。时间复杂度如果仅仅使用路径压缩的并查集，时间复杂度似乎并不是\(O(\alpha(n))\)，详情见这里。扩展域并查集yxc给出了一种简单易懂的理解扩展域并查集的方式：将并查集中的元素看成一个个条件，两个元素在一个集合中的意义是：如果有一个条件，那么整个集合中的条件都成立。我来形式化一点：并查集中的每一个元素都是一个语句\(p\)，每一个集合\(S\)都是一个命题：\(如果p(p\inS)，那么q(q\inS,q\not=p)。\)这样就十分容易理解了。例如：P2024[NOI2001
并查集简介并查集的两类操作：Get 查询任意一个元素是属于哪一个集合。Merge把两个集合合并在一起。基本思想：找到代表元。注意有两种方法：使用一个固定的值（查询方便，但是在合并的时候需要修改大量的值，比较复杂）使用树形结构，这样合并的时候可以直接让一个叫另一个eg.f[root1]=root2并查集的路径压缩以及按秩合并路径压缩：在每一次进行合并的时候，顺便更改每一个节点的值。（均摊复杂度：\(O(logN)\)）按秩合并：每一次查询的均摊复杂度是\(O(logN)\)。如果两个一起使用，那么最终的复杂度是线性的。但是正常使用路径压缩就行。使用并查集来维护具传递性的性质仅仅维护具有传递性：A
并查集简介并查集的两类操作：Get 查询任意一个元素是属于哪一个集合。Merge把两个集合合并在一起。基本思想：找到代表元。注意有两种方法：使用一个固定的值（查询方便，但是在合并的时候需要修改大量的值，比较复杂）使用树形结构，这样合并的时候可以直接让一个叫另一个eg.f[root1]=root2并查集的路径压缩以及按秩合并路径压缩：在每一次进行合并的时候，顺便更改每一个节点的值。（均摊复杂度：\(O(logN)\)）按秩合并：每一次查询的均摊复杂度是\(O(logN)\)。如果两个一起使用，那么最终的复杂度是线性的。但是正常使用路径压缩就行。使用并查集来维护具传递性的性质仅仅维护具有传递性：A
本题为1月1日22寒假集训每日一题题解题目来源:(未知)题面题目描述有n个城市和m条道路，每条道路连接两个城市。每条道路都是单向的，但你可以决定每条道路的方向。一个城市如果没有通向它的道路，就被认为是独立的，但允许有从这个城市通往其他城市的道路。请问最小的独立城市的数量。输入第一行输入两个数字n,m。表示城市的数量和道路的数量。接下来m行每行两个数字u,v,表示u,v两座城市中有一条道路相连。(2 ≤ n ≤ 100 000,1 ≤ m ≤ 100 000).输出输出一个数字，表示独立城市的最小数量。样例输入【样例输入1】43211343【样例输入2】552113232543【样例输入3】65
本题为1月1日22寒假集训每日一题题解题目来源:(未知)题面题目描述有n个城市和m条道路，每条道路连接两个城市。每条道路都是单向的，但你可以决定每条道路的方向。一个城市如果没有通向它的道路，就被认为是独立的，但允许有从这个城市通往其他城市的道路。请问最小的独立城市的数量。输入第一行输入两个数字n,m。表示城市的数量和道路的数量。接下来m行每行两个数字u,v,表示u,v两座城市中有一条道路相连。(2 ≤ n ≤ 100 000,1 ≤ m ≤ 100 000).输出输出一个数字，表示独立城市的最小数量。样例输入【样例输入1】43211343【样例输入2】552113232543【样例输入3】65
一、并查集概念并查集是一种树形的数据结构，顾名思义，它用于处理一些不交集的合并及查询问题。它支持两种操作：查找（Find）：确定某个元素处于哪个子集，单次操作时间复杂度O(α(n))，即查询元素p和元素q是否属于同一组合并（Union）：将两个子集合并成一个集合，单次操作时间复杂度O(α(n))，即合并元素p和元素q所在的组以下是并查集的常用模板，需要熟练掌握。其中：n表示节点数p存储每个点的父节点，初始时每个点的父节点都是自己size只有当节点是祖宗节点时才有意义，表示祖宗节点所在集合中，点的数量find(x)函数用于查找x所在集合的祖宗节点union(a,b)函数用于合并a和b所在的集合二
一、并查集概念并查集是一种树形的数据结构，顾名思义，它用于处理一些不交集的合并及查询问题。它支持两种操作：查找（Find）：确定某个元素处于哪个子集，单次操作时间复杂度O(α(n))，即查询元素p和元素q是否属于同一组合并（Union）：将两个子集合并成一个集合，单次操作时间复杂度O(α(n))，即合并元素p和元素q所在的组以下是并查集的常用模板，需要熟练掌握。其中：n表示节点数p存储每个点的父节点，初始时每个点的父节点都是自己size只有当节点是祖宗节点时才有意义，表示祖宗节点所在集合中，点的数量find(x)函数用于查找x所在集合的祖宗节点union(a,b)函数用于合并a和b所在的集合二
