关键词：
并查集：
(Kruscal)，(Tarjan)求(LCA)
分类并查集：食物链，团伙（敌人的敌人是我的朋友）
带权并查集：(SDOI2016)齿轮（可用
int father(int x)
return fa[x]==x?x:fa[x]=father(f[x]);
Luogu3101 滑雪等级[]
建边：任意相邻两格子之间建边，权值为海拔差
将边排序，从小往大一个一个往里加，当一个并查集内部有起点，并且大小（点数）>=T，这里面所有的起点的D=最后加入的边
#include<bits/stdc++.h>
using namespace std;
inline int read()
int ans=0;
char last=' ',ch=getchar();
while(ch>'9'||ch<'0') last=ch,ch=getchar();
while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
if(last=='-') ans=-ans;
return ans;
int m,n,T,ecnt;
int a[520][521],siz[500100],fa[500100];
long long LSY[500100];
struct node
int u,v,w;
e[500100];
int ykyk(int x,int y)
return (x-1)*n+y;
void insert(int x,int y,int dis)
ecnt++;
e[ecnt].u=x;
e[ecnt].v=y;
e[ecnt].w=dis;
bool cmp(node a,node b)
return a.w<b.w;
int find(int x)
if(fa[x]==x) return x;
int p=fa[x];
fa[x]=find(fa[x]);
if(LSY[x]==-1) LSY[x]=LSY[p];
return fa[x];
int main()
m=read();
n=read();
T=read();
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
a[i][j]=read();
for(int i=1;i<=m;i++)
for(int j=1;j<n;j++)
insert(ykyk(i,j),ykyk(i,j+1),abs(a[i][j]-a[i][j+1]));
for(int i=1;i<m;i++)
for(int j=1;j<=n;j++)
insert(ykyk(i,j),ykyk(i+1,j),abs(a[i][j]-a[i+1][j]));
for(int i=1;i<=n*m;i++) fa[i]=i,siz[i]=1;
sort(e+1,e+ecnt+1,cmp);
memset(LSY,-1,sizeof(LSY));
for(int i=1,p,q;i<=ecnt;i++)
p=find(e[i].u);q=find(e[i].v);
if(p!=q)
if(siz[p]+siz[q]>=T)
if(siz[p]<T)
LSY[p]=e[i].w;
if(siz[q]<T)
LSY[q]=e[i].w;
if(siz[q]<siz[p]) swap(p,q);
fa[p]=q;
siz[q]+=siz[p];
long long LYT=0;
for(int i=1,k;i<=m*n;i++)
k=read();
if(k)
find(i);
LYT+=LSY[i];
printf("%lld
",LYT);
return 0;
BZOJ 1015 星球大战
很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。
但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始不可靠起来。现在，反抗军首领交给你一个任务：给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序，以尽量快的速度求出每一次打击之后反抗军占据的星球的连通快的个数。（如果两个星球可以通过现存的以太通道直接或间接地连通，则这两个星球在同一个连通块中）。
反过来考虑，一个一个星球往上加
把所有询问离线下来，倒着做。
POJ 1703 Find them，Catch them[]
建(2n)个点，前(n)个点表示在第一个帮派中，后(n)个表示在第二个帮派中
如果(1,2)不在同一个帮派中，将第一个帮派中的第一个人和第二个帮派第二个人，第一个帮派中的第二个人和第二个帮派第一个人连起来
敌人的敌人就是朋友
(D) (a) (b) 连接((a,b+n)(a+n,b))
(A) (a) (b) 如果((a,b) (a+n,b+n))在同一个并查集，则是同一个帮派
如果((a,b+n)(b,a+n))在同一个并查集，则是不同帮派
其余的不能确定
POJ 1182 食物链[]
动物王国中有三类动物(A,B,C)，这三类动物的食物链构成了有趣的环形。(A)吃(B)，
(B)吃(C)，(C)吃(A)。
现有(N)个动物，以(1－N)编号。每个动物都是(A,B,C)中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这(N)个动物所构成的食物链关系进行描述：
第一种说法是"1 (X) $ Y("，表示)X(和)Y$是同类。
第二种说法是"2 (X) (Y)"，表示(X)吃(Y)。
此人对(N)个动物，用上述两种说法，一句接一句地说出(K)句话，这(K)句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1）当前的话与前面的某些真的话冲突，就是假话；
2）当前的话中(X)或(Y)比(N)大，就是假话；
3）当前的话表示(X)吃(X)，就是假话。
你的任务是根据给定的(N（1<= N <= 50,000）)和(K)句话(（0 <= K <= 100,000）)，输出假话的总数。
开三个并查集：
(colorYellow同类 colorRed捕食)：
如果(a)和(b)是同类，则a的三个节点((a,a+n,a+2n))分别指向(b)的对应的三个节点((b,b+n,b+2n))
如果(a)吃(b)，则(a)的三个节点分别指向对应(b)的三个节点的下一个节点
#include<bits/stdc++.h>
using namespace std;
inline int read()
int ans=0;
char last=' ',ch=getchar();
while(ch>'9'||ch<'0') last=ch,ch=getchar();
while(ch>='0'&&ch<='9') ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
if(last=='-') ans=-ans;
return ans;
const int mxn=50010;
int n,k;
int cnt,ans;
int fa[mxn*3];
int find(int x)
if(fa[x]==x) return x;
fa[x]=find(fa[x]);
return fa[x];
int main()
n=read();
k=read();
for(int i=1;i<=3*n;i++) fa[i]=i;
for(int i=1,op,x,y;i<=k;i++)
op=read();
x=read();
y=read();
if(y>n||x>n)
ans++;
continue;
if(op==2&&x==y)
ans++;
continue;
if(op==1)
if(find(x)==find(y+n)||find(x)==find(y+2*n))
ans++;
continue;
int xx=find(x),yy=find(y);
fa[xx]=yy;
int _x=find(x+n),_y=find(y+n);
fa[_x]=_y;
int x_=find(x+2*n),y_=find(y+2*n);
fa[x_]=y_;
if(op==2)
if(find(x+2*n)==find(y)||find(x)==find(y))
ans++;
continue;
int xx=find(x),yy=find(y);
int _x=find(x+n),_y=find(y+n);
int x_=find(x+2*n),y_=find(y+2*n);
fa[yy]=_x;
fa[xx]=y_;
fa[x_]=_y;
printf("%d",ans);
return 0;
并查集相关：
(BZOJ) (2303) ([Apio2011]) 方格染色
(BZOJ) (1854) ([SCOI2010]) 游戏
带权并查集：
(HDU)(3038) (How) (Many) (Answers) (Are) (Wrong)
(HihoCoder) (1515) 分数调查
[qbzt寒假]线段树和树状数组(代码片段)
树状数组(lowbit(x)=x&(-x))二维树状数组修改某个点，查询(1,1)到(n,m)的前缀和（树状数组要从1开始）HDU2642Stars(YFF)是个浪漫的人，他喜欢数天上的星星。为了解决这个问题，我们考虑到天空是一个二维平面，有时星星会很亮，有... 查看详情
并查集(代码片段)
主要内容本文主要记录并查集的基本实现方法，并逐步将一些例题填充到文章中。并查集能做什么并查集可以：1.合并集合2.查找两个元素是否在同一个集合内3.集合数量4.确定元素属于哪个集合。完整代码示例classUFpublic:UF();UF(int... 查看详情
markdown并查集(代码片段)
golang并查集(代码片段)
并查集p3367模板并查集(代码片段)
P3367【模板】并查集#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>usingnamespacestd;intn,m,zi,xi,yi;intfather[10001] 查看详情
数据结构----并查集(代码片段)
并查集并查集概念并查集的模拟实现模拟实现并查集优化Union优化压缩路径循环递归并查集例题并查集概念并查集在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集... 查看详情
并查集——新手学习记录(代码片段)
好吧，什么垃圾并查集，并查集什么的都是铁憨憨<+__+>现在开始复习回忆：（新手，有错误望指正）什么叫做并查集，并查集就是一个集合问题，其实最主要的就是知道并查集是一个求解集合数目的问题，具体的操作方法有... 查看详情
并查集原理分析(代码片段)
文章目录1.并查集是什么2.并查集性质3.并查集可以解决的问题4.并查集模板5.并查集的应用1.并查集是什么在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时**，每个元素自成一个单元素集合**... 查看详情
数据结构--并查集(代码片段)
并查集并查集原理并查集实现并查集原理在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要... 查看详情
关于并查集的一切全在这里了(代码片段)
文章目录并查集初识「并查集」常用术语「并查集」基本思想「并查集」的两个实现方式QuickFind方式实现并查集QuickFind工作原理：代码实现与验证时间复杂度QuickUnion方式实现并查集QuickUnion的工作原理为什么QuickUnion比QuickFind... 查看详情
数据结构----并查集(代码片段)
并查集并查集概念并查集的模拟实现模拟实现并查集优化Union优化压缩路径循环递归(深度过深有栈溢出的风险)并查集例题并查集概念并查集在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每... 查看详情
并查集(代码片段)
本文参考了【算法】并查集（DisjointSet）和并查集详解并查集原理并查集是一种用于处理不相交集合之间合并问题的数据结构，例如求连通子图、判断是否存在环、求最小生成树等。以判断图中是否有环为例，下图是一个无向图... 查看详情
dzyloveschemistry（并查集）(代码片段)
题目：（??，最近净做并查集了还一道难的都不会）DZYloveschemistry,andheenjoysmixingchemicals.DZYhasnchemicals,andmpairsofthemwillreact.Hewantstopourthesechemicalsintoatesttube,andheneedstopourtheminonebyone,inanyorder.Let‘sc 查看详情
树的应用——并查集及实现代码(代码片段)
文章目录什么是并查集亲戚问题并查集的实现改进——路径压缩进一步改进——合并并查集的用途什么是并查集 并查集是一种树型的数据结构，用于处理一些不相交集合（disjointsets）的合并及查询问题。常常在使用... 查看详情
并查集(入门)(代码片段)
首先先看一道很简单的并查集的题目：https://vjudge.net/contest/297398#problem/A这道题就是让你判断两两城镇之间是否联通 如果不联通就要修建一条道路 就我的理解来说，如果单独使用并查集就是为了合并有相同根结点(或者理... 查看详情
并查集(代码片段)
/*并查集*/#include<stdio.h>int*a;int*sz;intcount;//thenumberofconnectedcomponent//uniontwoconnectedcomponentswithweightsvoidunion_two_points(intp,intq)inti=root(p);intj=root(q);if(i==j)return;if(s 查看详情
并查集(代码片段)
...们看两道题 亲戚 朋友 显然我们需要并查集。 So,什么是并查集？ 并，就是合并关系（也就是认祖宗）。查，就是查找关系（就是看祖宗是不是一个人）。集，是因为它是个集合。 并查集怎么写呢... 查看详情
树--12---并查集(代码片段)
文章目录并查集并查集是一种树型的数据结构并查集结构1.并查集的实现API设计UF(intN)构造方法实现union(intp,intq)合并方法实现代码：测试：案例1:计算机网诺连接2.UF_Tree算法优化eleAndGourp数组API设计find(intp)查询方法实现unio... 查看详情