普通并查集模板
int par[1010],high[1010];
void init(int n)
{
for(int i=1;i<=n;i++)
{
par[i]=i;
high[i]=0;
}
}
int find(int x)
{
if(par[x]==x)return x;
return par[x]=find(par[x]);
}
void unite(int x,int y)
{
x=find(x);
y=find(y);
if(x==y)return;
if(high[x]<high[y])par[x]=y; //启发式合并
else
{
par[y]=x;
if(high[x]==high[y])high[x]++;
}
}
bool same(int x,int y)
{
return find(x)==find(y);
}带权并查集模板
int par[10010],high[10010];//保存奇偶
void init()
{
for(int i=0;i<10010;i++)
{
par[i]=i;
high[i]=0;
}
}
int Find(int x)
{
if(par[x]==x)return x;
int tmp=par[x];
par[x]=Find(par[x]);
high[x]=(high[x]+high[tmp])%2; //把沿途子节点的所有父节点的权值处理一下，比如本来high[x]和high[temp]相反，就相反一下
return par[x];
}
int unite(int x,int y,int z)
{
int px=Find(x);
int py=Find(y);
if(px==py)
{
if(high[x]==(high[y]+z)%2)return 0; //判断是否符合奇偶
return 1;
}
par[py]=px;
high[py]=(high[x]-high[y]+z+2)%2; //可能是负的，所以要+2
return 0;
}
bool same(int x,int y)
{
return Find(x)==Find(y);
}HDU 1213
为啥用set就错了???
POJ 1182
题意：
三类动物A、B、C构成食物链循环，告诉两个动物的关系（同类或天敌），判断那个关系是和前面已有的冲突。
解题思路：
对于每只动物i创建3个元素i-A, i-B, i-C, 并用这3*N个元素建立并查集。这个并查集维护如下信息：对于1，合并x-A和y-A、x-B和y-B、x-C和y-C；对于2，合并x-A和y-B、x-B和y-C、x-C和y-A。不过在合并之前需要先判断合并是否会产生矛盾。例如在第一种信息的情况下，需要检查比如x-A和y-B或者y-C是否在同一组等信息。
POJ 1308
题意：
判断有向图是否成树。
解题思路：
成树的条件：不能有环（只要判断x,y的根是否是同一个即可），顶点数=边数-1，每个顶点的入度<=1，自己不能指向自己。
HDU 3038
题意：
有n次询问，给出a到b区间的总和，问这n次给出的总和中有几次是和前面已近给出的是矛盾的。
解题思路：
int find(int x)
{
if(par[x]==x)return x;
int tmp=par[x];
par[x]=find(par[x]);
high[x]=high[x]+high[tmp]; //把沿途子节点的所有父节点的权值都加上
return par[x];
}
因为要知道每个点到根的距离，所以可以路径压缩。
合并点的时候如果同个根的话就判断一下，其他就合并一下，把右边的树的根向左边树的根连边，更新一下根的相关标记就可以了。
int unite(int x,int y,int z)
{
int px=find(x);
int py=find(y);
if(px==py)
{
if(high[x]+z==high[y])return 0;
else return 1;
}
par[py]=px;
high[py]=high[x]-high[y]+z;
return 0;
}POJ 1733
题意：
给一个序列这个序列都是由0和1组成，现在随意拿出来一个序列，然后说出他的和是奇数还是偶数，因为有可能存在假话，让你判断前多少条没有假话，也就是查找第一个假话的位置-1。
解题思路：
带权并查集+离散化。带权部分和上题相似。在unite的时候判断是否符合奇偶利用奇偶性，在更新连过去的根的high[i]的时候，因为high[py]=(high[x]-high[y]+z+2)%2;，括号里面可能是负的，所以要+2，find函数中high[x]=(high[x]+high[tmp])%2;（把沿途子节点的所有父节点的权值处理一下，比如本来high[x]和high[temp]相反，就相反一下）。离散化部分可以用map来映射一下，key存该数字，value存下标（注意后面是mp[a]==0所以下标从1开始）。
还是把草稿纸拍下来比较清楚吧www
POJ 1456
题意：
有N件商品，知道了商品的价值和销售的最后期限，只要在最后日期之前销售处，就能得到相应的利润，并且销售该商品需要1天时间，求出最大利润。
解题思路：
直接贪心就可以水过，但是这里可以用并查集优化，优化的是先把所有产品按照利润从大到小排序，然后看截止日期这种情况，par[i]里面放截止日期，如果这个截止日期被占用了的话，就往前推，表示如果再有截止日期为这个日期的物品的话，这个物品找根的时候就是日期往前推，par[i]=i-1，对于每一个p[i].t，先找一下它的根，如果根>0的话，就说明可以用。
POJ 2912
题意：
给出n个人玩剪刀石头布的游戏，其中有一个人是裁判，剩下的人分为3组，每一组的人只出某一种手型，裁判可以任意出。问是否能判断出哪个人是裁判。
解题思路：
食物链的做法就可以了，这里要判断裁判，就枚举每一个人，与他相关的局数就跳过去，如果这个人是裁判的时候没有出错的话，就说明这个人可能是裁判了，如果有多种裁判情况的话，就输出Can not determine；如果没有裁判的话，输出Impossible；只有一个裁判的话，就输出其他所有的出错局数最大的。
ZOJ 3261
题意：
有一些点，还有一些边，每个点上都有一个权值，然后有一些询问，分为两种，query a 询问与a直接或者间接想连的点中最大权值的是那个点，输出那个点，如果那个点的权值小于等于a的权值，那么就输出-1，还有另一种操作就是destroy a b意思是删除a b的关系。
解题思路：
并查集不能实现删边操作，所以就倒着来，先删掉所有该删的边之后，倒着来回答问题，如果遇到删边的话，就添边即可。
POJ 1984
题意：
有多个点，在平面上位于坐标点上，给出一些关系，表示某个点在某个点的正东/西/南/北方向多少距离，然后给出一系列询问，表示在第几个关系给出后询问某两点的曼哈顿距离，或者未知则输出-1。
解题思路：
带权并查集。跟之前的题目都差不多，只不过变成二维的了。
POJ 1417
题意：
有这么一群人，一群好人，和一群坏人，好人永远会说实话，坏人永远说假话，现在给你一组对话和好人与坏人的数目P1， P2。数据里面的no是A说B是坏人， yes代表A说B是好人，就是这样，问题能不能从这些话里面得出来唯一的解，就是可以确定谁是好人谁是坏人，如果不能输出no，如果可以输出所有的好人。
解题思路：
如果两个人是yes的话，就说明是同类，如果两个人是no的话，说明不是同类，用带权并查集合并（这样相对于只有同类合并会少几个集合），然后判断是否唯一，每个集合又分成两个小集合表示两种类型的个数，而我们要求的是在所有大集合中选出一个小集合然后加起来看能不能组 合成p1，并且要唯一，这里我们可以想到用背包来做，dp[i][j]表示前i个大集合好人为j个的方案数，第i种状态只能由第i-1种状态而来，我们用w0[i],w1[i]表示第i个集合两个小集合的个数 ，所以dp[i][j]可以由dp[i-1][j-w0[]i]和dp[i-1][j-w1[i]]得来，这样我们只需判断dp[cnt][p1]是否等于1，这题还有麻烦的就是输出好人的编号，这里我们可以利用边的权值，w0存的全是权值为0的，w1存的全是权值为1的，然后最后只需判断下第i个集合是由w0还是w1组合而来，这里可以利用dp[i-1][p1-w0[i]]的值来判断，如果等于1则表示是由w0组合否则就是w1，dp[i-1][p1-w0[i]]==1可以得到dp[i][p1]==1，因为这里已经表示答案唯一，所以只有一种情况！本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！