并查集并查集是一种用于处理不相交集合的合并与查询问题的数据结构，在C++中有着广泛的应用，以下是关于C++中并查集的详细介绍：基本概念集合表示：并查集将每个集合用一棵树来表示，树中的节点代表集合中的元素，树根作为集合的代表元素。合并操作：把两个集合合并为一个集合，通过

普通并查集 板子：voidfind(intx){ if(f[x]==x)returnx; returnf[x]=find(f[x]);}voidmerge(intx,inty){ intfx=find(x),fy=find(fy); if(fx!=fy)f[fx]=fy;} 具体几个应用：1.找图中联通块的个数 扩展一下，问图最小需要多少条边联通。  原题

食物链  题目  提交记录  讨论  题解  视频讲解动物王国中有三类动物 A,B,CA,B,C，这三类动物的食物链构成了有趣的环形。AA 吃 BB，BB 吃 CC，CC 吃 AA。现有 NN 个动物，以 1∼N1∼N 编号。每个动物都是 A,B,CA,B,C 中的一种，但是我们并不知道它到

题目链接：https://www.luogu.com.cn/problem/P1111题意：有n个村，给你m个信息，1个信息包含存在道路的两个村子以及通路的时间，让你求是否每个村子都能相连，若能相连输出通路最短时间思路：并查集+排序在一个集合中的村子能够相互连通，所以就看本来并查集n个独立的集合能不能通过所给操

题目链接：P1525[NOIP2010提高组]关押罪犯-洛谷|计算机科学教育新生态题目难度：普及+/提高题目描述：S城现有两座监狱，一共关押着 N 名罪犯，编号分别为 1∼N，有m对罪犯，每对之间有仇恨值，问如何分配罪犯使得现Z市长要看到其中最大的矛盾值最小。输入格式：每行中两个数之

并查集模板：#include<iostream>#include<vector>usingnamespacestd;//初始化父节点数组vector<int>fa;//查找根节点并进行路径压缩intfindParent(intx){if(x==fa[x])returnx;returnfa[x]=findParent(fa[x]);}//合并两个集合voidunionS

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'#definexfirst#defineysecond#defineintlonglongconstintN=1e6+10,mod=998244353;intf[N],w[N];//w[i]表示i这个点比根节点的值大多少intfind(intx){ if(f[x]==x)returnx; intp

前言打卡代码随想录算法训练营第49期第五十五天(～￣▽￣)～首先十分推荐学算法的同学可以先了解一下代码随想录，可以在B站卡哥B站账号、代码随想录官方网站代码随想录了解，卡哥清晰易懂的算法教学让我直接果断关注，也十分有缘和第49期的训练营大家庭一起进步。学习今天的课程前，先看并

线段树分治（时间线段树）线段树分治是一种离线的算法，按时间分治。常用于处理每个操作有一定的生效时间（或者每个查询限制一段时间）的题目。其本质是钦定良好的顺序来得出答案，使得执行操作的次数最少。而对于具有类似思想的trick有：对于一些图论问题，可以将操作离线，然后对于每一个操

开拓计划4-二叉树与并查集二叉树二叉树的概念Q：什么是树？A：一种有\(n\)个节点最多有\(n-1\)条边的图。Q：什么是二叉树？A：每个节点都最多只有两个子节点的树。二叉树和递归Q：二叉树和递归有什么关系？A：在执行递归的时候总是会自己调用自己，每一次调用都会产生新的一层，新

NKOJ1209并查集【NOI2001Day1T3】食物链思路：带权/种类并查集方法一实现方法用带权并查集带的权值是边权，不是点权，用来表示两点间的关系，但为了方便记录还是用点权，每个点记录到根节点的权值。在getf函数中注意更新是到根节点之间的权值，用\(val_x=(val_x+val_{fa_x})\bm

NKOJ2107【并查集】可爱的猴子思路：普通并查集+图的遍历更新答案实现方法首先使用时光倒流思想解决删边的问题。注意提前把没有删过的边提前建上。接着用一个图记录猴子之间的拉手关系，每次要更新答案时都遍历与当前节点连着的节点将其答案更新，只有在\(1\)号节点与当前节

标题最小生成树时间限制2S内存限制10000Kb问题描述：用克鲁斯卡尔（Kruskal）算法求无向网的最小生成树。输入：输入数据第一行为两个正整数n（1<n<=30）和m（1<m<100），分别表示顶点数和边数。后面紧跟m行数据，每行数据是一条边的信息，包括三个数字，分别表示该边的两个顶点和边上的权值

classSolution{unordered_map<int,int>fa,rank;voidinit(unordered_set&set){for(constauto&num:set){fa[num]=num;rank[num]=1;}}intfinds(intx){if(x!=fa[x]){fa[x]=finds(fa[x]);}returnfa[x];}voidunions(intx,inty){introotx=f

你是否曾为如何高效地解决图论中的连通性问题而烦恼？并查集算法，就像一张无形的网，能帮你轻松连接所有节点。今天，就让我们一起揭开并查集算法的神秘面纱，探索它在Java编程中的应用。并查集是什么？并查集（Union-Find）是一种数据结构，用于处理一些不交集的合并及查询问题。它支持两

一、例题引入洛谷P3367【模板】并查集题目描述如题，现在有一个并查集，你需要完成合并和查询操作。输入格式第一行包含两个整数$N,M$,表示共有$N$个元素和$M$个操作。接下来$M$行，每行包含三个整数$Z_i,X_i,Y_i$。当$Z_i=1$时，将$X_i$与$Y_i$所在的集合合并。

importjava.util.HashMap;classSolution{publicstaticHashMap<Integer,Integer>row=newHashMap<>();publicstaticHashMap<Integer,Integer>col=newHashMap<>();publicstaticintMAXN=1001;publicstati

classSolution{publicstaticintMAXN=90001;publicstaticint[]f=newint[MAXN];publicstaticintn=0;publicstaticintunion_count=0;publicstaticbooleanisSameSet(inti,intj){returnfind(i)==find(j);

基础算法贪心[lnsyoj4029/luoguP4109/HEOI2015]定价[lnsyoj2271/luoguP3745/省选联考2017]期末考试莫队普通莫队[luoguSP3267]D-query[luoguP1494]小Z的袜子带修莫队[luoguP1903]数颜色树上莫队[luoguSP10707]CountonatreeII[luoguP4074/WC2013]

普通并查集就是开一个\(fa[i]\)数组表示\(i\)的祖先节点。初始化for(inti=1;i<=n;i++)fa[i]=i,siz[i]=1;//fa[i]初始状态一定是只像自己的,siz[i]:表示以i为根的子树大小查询inlineintgetf(intx){if(x==fa[x])returnx;returngetf(fa[x]);}合并

>1樱子的爱好题目https://codeforces.com/contest/2008/problem/D思路以5413210011为例i=1,p1=5,s5=1-->i=5,p5=2,s2=0-->i=2,p2=4,s4=1-->i=4,p4=3,s3=0-->i=3,p3=1,s1=1无论i=1还是5，2，4，3，最终黑色的个数都一

[复习]种类并查集种类并查集也可叫做扩展域并查集。前言自从两年多前刚学并查集时过了食物链后，就再也没有写过种类并查集。今天回顾一下。例题1食物链P2024[NOI2001]食物链。题目大意：有\(n\)个动物，每个动物属于\(A,B,C\)种中的一种，\(A\)吃\(B\)，\(B\)吃\(C\)，\(

大概叫这个名字吧https://atcoder.jp/contests/abc380/tasks/abc380_e#include<bits/stdc++.h>#defineendl'\n'#definelowbit(x)(x&-x)usingnamespacestd;typedeflonglongll;typedefpair<int,int>pii;typedefpair<ll,ll>pll;c

板子intfind(intx);voiduniona(intx,inty);------------------------------------------------------------intp[N],r[N]={0};//p是父亲数组，r是根节点的深度for(inti=1;i<=n;i++)p[i]=i;//初始化intp1=find(a),p2=find(b);//单独写出来，避

题目背景若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。题目描述规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x，y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。输入格式