并查集与类型推导 - 简书
并查集与类型推导
某次参加笔试的最后一题大意如下：给定一组用户[0..n]，以及他们之间的好友关系，问这些好友构成了多少个朋友圈？例如有用户[1..5]，好友关系有(1,2),(3,4),(4,5)，则共有两个好友圈：[1,2]和[3,4,5]
题目的意思可以理解为给定一个无向图，求其中连通子图的个数。算法来自于《算法导论（第二版）》的第21章对于一个并查集来说，我们通常希望其支持三种操作：MakeSet(x)：当我们新加入一个元素，且与当前任何节点有连接，因此它（目前为止）单独成为一个集合。Union(x,y)：添加两个元素之间的联系，因此两个元素属于的集合需要合并成为一个集合。FindSet(x)：查询一个元素到底属于哪个集合。显然当有n个元素时，Union操作至多有n-1次，MakeSet操作至多为n次。
可以用一个数组p来储存所有元素对应的集合。例如p[x]=1表示元素x属于编号为1的集合。然而整个编号为1的集合可能又属于另一个更大的集合，因此需要查询p[1]来找到其父集合……以此类推，直到有p[a]=a为止。由此可见，这其实是一种基于树的实现。
图片源自《算法导论》
按秩合并(union by rank)rank可以看作是每个根节点的高度（并不严格是，其实是其高度的一个上界），合并两棵树树时，将高度较小的树的根指向高度较大的树可以保证合并后的树的高度上界不再增加。若高度相等，则合并后的树高度加一。
路径压缩(path compression)当从某一结点以此查找到根节点时，可以将经过路径的所有节点的父节点都修改为根节点。但我们的方法中并不修改根节点的秩，因为修改一颗树的高度需要遍历整棵树的所有节点才能确定，这显然得不偿失，这也就解释了为什么秩并不是每棵树的高度，而是它高度的一个上界。
图片源自《算法导论》
int MakeSet(int x)
rank[x]=0;
void Union(int a,int b)
int x=FindSet(a);
int y=FindSet(b);
if(rank[x]&rank[y])
if(rank[x]==rank[y])
rank[y]=rank[y]+1;
int FindSet(int x)
if(x!=p[x])
p[x]=FindSet(p[x]);
return p[x];
若MakeSet、Union和FindSet操作共m个，其中有n个MakeSet操作，单独使用按秩合并的策略运行时间为
单独使用路径压缩，若有n个MakeSet操作和f个FindSet操作，运行时间为
在一个函数体中，各个参数的相互作用可以看作是一个无向有环图（DAG）。依据函数内的各个节点，可以生成一系列的类型约束等式。
图片来自Essentials of Porgramming languages
图中的代码proc(f)proc(x)-((f 3),(f x))等价于如下scheme代码：
(lambda (f) (lambda (x) (- (f 3) (f x))))
或者如下C++代码
template&typename T3,typename Tf,typename Tx&
T3 func(Tf f, Tx x)
return (f 3)-(f x);
约束生成(constraints generation)的规则如下：
内容来自Programming Languages and Lambda Calculi
得到类型等式后，接下来是对等式进行合一(unify)和替换(substitute)操作。合并规则如下：
内容来自Programming Languages and Lambda Calculi
关于多态的推导：
内容来自Programming Languages and Lambda Calculi
下面是Essentials of Programming Languages中的步骤演示
可以看到，每一个等式，都需要进行unify操作，因为类型相等即代表它们属于同一集合。但需要注意的是，这里的unify操作和之前提到的union并不完全相同，因为我们还需要处理函数类型。若有类似t1-&t2=t3-&t4的等式，则需要同时unify(t1,t3)和unify(t2,t4)。另一方面，在合并类型时可能是有方向的，需要将泛化(generic)类型向具化(normalized)类型合并。例如有t1=t2,t2=int，则得到t1=int,t2=int，这也意味这上文提到的按秩合并的策略在此并不可用，但路径压缩依然可行。
《算法导论》中关于并查集算法时间复杂度的证明
Hindley-Milner类型系统
逻辑式编程与合一算法
Recursive Type（本文中的类型推导仅对STLC(simply typed lambda calculus)成立，根据STLC的strong normalization特性，所有STLC能表达的程序中不会有递归且一定终止，如果突破这一限制呢？）并查集的前因后果 - 综合当前位置:& &&&并查集的前因后果并查集的前因后果&&网友分享于：&&浏览：2次并查集的来龙去脉1 并查集的思想：
& & 已知：
& & &1）很多个元素有着一个属性值，这些属性与其他元素的属性值或相同或不相同；
& && 2）我们不知道每个元素的属性值，但知道一些两个元素之间属性值相等的关系——等价关系（有自反性，对称性，传递性）；
& & & 根据等价关系将所有元素划分到对应的等价类中去，每个等价类中的元素两两之间都存在着等价关系。
& & &算法：
& & &1）将所有的元素初始化为独立的集合；
& & &2）根据元素间的等价关系，将对应的元素所在的集合合并Union操作。如何合并？我们给每个集合自定义一个集合值来表示其中的元素属性。Union所需的操作即把原来两个分开的集合的两个集合值改为一个相同的集合值则。我们已知等价关系中的两个元素，需要一个Find方法来查询这个集合值，再将这两个集合值修改为一个值；
& & &并查集是可用树来实现，其实也可以其他的实现方法。比如:
& & 1）.可用额外一个标记数组来表示属性，而不用代表元素来表示属性。当然，那样Union的复杂度会大大提高O(n)，但find的复杂度会降低O(1);
& & &2）.可用多个vector来表示不同的集合。集合的合并的实现为：建立新的vector将原来两个vector的元素都拷贝过来。然后销毁原来的两个vector。那么集合值就是vector的地址。这种理解最直观。无疑，这种方法的效率最低。Union和find的复杂度都为O(n)；
& & & 3）用树来实现集合（这也是集合的最常见的实现数据结构）。则可用树的根节点来表示元素值。这样Union操作大大的简化了，只需让一个集合的根节点指向另一个集合的根节点即可——O(1)。当然，find的复杂则达到了近似O(log2 n）。
& 树的实现是最理想的。树只是一种逻辑结构，出于方便。我用了STL的关联数组来实现。
class UnionFindSet
string find(string str);
unite(string str1,string str2);
void initial(string str1);
map&string,string& _union_find_
void UnionFindSet::initial(string str1)
_union_find_set[str1]=string(&-1&);
string UnionFindSet::find(string str)
string father=
father=_union_find_set[str];
}while(father[0]!='-'&&!father.empty());
if(father.empty())
initial(str);
bool UnionFindSet::unite(string ancestor1,string ancestor2)
int size1,size2;
if(ancestor1==ancestor2)
//C++11 is not support in gcc 4.6
//size1=stoi(_union_find_set[ancestor1]);
//size2=stoi(_union_find_set[ancestor2]);
size1=atoi(_union_find_set[ancestor1].c_str());
size2=atoi(_union_find_set[ancestor2].c_str());
if(size1&=size2){
_union_find_set[ancestor1]=ancestor2;
ss&&size1+size2;
_union_find_set[ancestor2]=ss.str();
_union_find_set[ancestor2]=ancestor1;
ss&&size1+size2;
_union_find_set[ancestor1]=ss.str();
&可用并查集来解决很多问题。Kruskal算法，判断图是否含有环。这两个问题的算法都需要归并不同的联通分量。与并查集用于归并集合的用途吻合。
还可用并查集来处理二分图问题。这个问题其实就是判断图是否有包含奇数个节点的环的问题。代码如下，需要添加一个bCircleNodeNumOdd方法：
#include &stdio.h&
#include &stdlib.h&
#include &unistd.h&
//#include &ext/map&
#include &map&
#include &string&
#include &iostream&
#include &sstream&
//using namespace __gnu_
class UnionFindSet
string find(string str);
unite(string str1,string str2);
void initial(string str1);
bool bCircleNodeNum(string str1,string str2);
map&string,string& _union_find_
bool UnionFindSet::bCircleNodeNumOdd(string str1,str2)
void UnionFindSet::initial(string str1)
_union_find_set[str1]=string(&-1&);
string UnionFindSet::find(string str)
string father=
father=_union_find_set[str];
}while(father[0]!='-'&&!father.empty());
if(father.empty())
initial(str);
bool UnionFindSet::unite(string ancestor1,string ancestor2)
int size1,size2;
if(ancestor1==ancestor2)
//C++11 is not support in gcc 4.6
//size1=stoi(_union_find_set[ancestor1]);
//size2=stoi(_union_find_set[ancestor2]);
size1=atoi(_union_find_set[ancestor1].c_str());
size2=atoi(_union_find_set[ancestor2].c_str());
if(size1&=size2){
_union_find_set[ancestor1]=ancestor2;
ss&&size1+size2;
_union_find_set[ancestor2]=ss.str();
_union_find_set[ancestor2]=ancestor1;
ss&&size1+size2;
_union_find_set[ancestor1]=ss.str();
int main(int argc,char **argv)
int t,m,i,j;
scanf(&%d&,&t);
for(i=0;i&t;++i){
scanf(&%d&,&m);
UnionFindS
bool b_checked=
for(j=0;j&m;++j){
string pair1,pair2;
cin&&pair1&&pair2;
if(b_checked)
if(set.find(pair1)==set.find(pair2)){
if(set.bCircleNodeNumOdd(pair1,pair2)){
printf(&Case #%d: No\n&,i+1);
// cout&&& Same father : &&&set.find(pair1)&&
b_checked=
set.unite(set.find(pair1),set.find(pair2));
if(!b_checked)
printf(&Case #%d: Yes\n&,i+1);
//printf(& m: % size:%d\n&,m,set._union_find_set.size());
12345678910
12345678910
12345678910 上一篇：下一篇：文章评论相关解决方案 12345678910 Copyright & &&版权所有: 森林结构的运用（poj： 树的转换，电话号码，物质分解记录）；带权并查集（食物链);C++输入；map的基本使用
本来是应该昨晚写这篇总结的，但无奈昨晚断网了，坑爹的校园网！！！~
昨天成功刷掉了树与森林的4道题，加上前天做掉的并查集入门题， 树与森林宣告终结！不过这一章的确学到很多东西，尤其是编程技巧和一些细节处理！
首先讲三道比较简单的吧， 主要就是考察森林的建立与一些基本操作， 包括与树，二叉树的相互转换，查找，更新等等。
森林的建立我目前比较熟悉且常用的是两种方式：
一种是数组存储， 需要用一个变量来记录当前数组的存储位置，每加入一个元素都得更新此变量，利用数组的下标作索引，十分方便，也不用担心指针的使用这种问题，因为根本用不上指针，我除了最开始的物质分解记录 后面都用的数组存储， 可能最开始使用会不习惯！~；（另外就是一定要仔细确定题目要求后来推出应该规定的数组最大容量，
否则会RE！因为这种存储方式无法动态分配！）
一种是链式存储，最白痴的存储方式，也是最万能的存储方式，实在找不到好的存储结构就用链式， 只不过动态操作内存有点麻烦，还有就是指针的使用容易出错， 改变指针指向时一定要注意是否有冲突！还有就是程序结束时或者每一组测试数据结束时要手动清空内存， 否则在数据量大时可能造成错误（虽然在计算机中整个程序结束时会自动执行清空操作，但那个不是你自己的程序的操作！！！）
两种方法只是在形式上差别比较大， 关于子节点索引表其实都是用相同的方式解决，因为子节点数目不定，可以用vector(顺序固定）， set(排好序）， map（方便根据一个key值来进行查找， 将搜索复杂度降到O（lgn），无论key是何种类型都适合！）。 注意set和map都会改变顺序， 而vector在需要大量查找操作时效率低下，基本上都会超时！
值得一提的是， 在为完全k叉树时，又可以采取另一种数组存储方式，前面的数组存储方式相当是将指针换成整数下标索引，而且基本上是深度优先存储， 而这个可以按照层遍历的顺序进行存储， 也不用记录节点索引下标， 因为存储时下标间的关系就被定好了，这种情况下用这种存储操作会十分方便，空间上索引值， 时间上比如想找到某个深度的元素， 不用遍历直接计算下标即可，所以说空间和时间上都被优化了！~
对于标号为i的节点（根为1）， 它的子节点是从k*i-(k-2)到k*i+1，
最后一层最后面一部分可能有些不存在！~ & & & & & & & & & & & & & & & & & & & & & & & & & &
它的父节点是(i-2)/k+1, & & & & & &注意正负都是向0取整！
这种存储方式只适合完全k叉树，否则是对存储空间的严重浪费！
懂得基本操作后就可以直接练习了，每道题中都有一些独特的地方， 物质分解记录 这道题中主要是一个数据读入方式的问题， 这就需要我们对各种输入方式了解清楚，特别是输入后光标的移动情况！！！ 关于输入问题的说明附在这道题的程序下方， 经过我自己逐个实验的，可以信赖！
Name: 物质分解记录
Copyright: poj
Author: xiaoli
Date: 30/10/13 11:00
Description:
1. 主要考察点是数据的读入以及森林结构的建立（这里森林使用链式存储建立，子节点索引采用vector）
数据的读入（尤其是整行的读入）在C++中是个大问题，程序下方是我关于这个的小总结
2. 一个很那发现的小错误：避免使用重复定义！！！我在此的错误是：循环外定义了i，循环中的计数变量采用的又是int i形式，
循环外部又需要用到循环后的i值， 但是重复定义时采取的是层次划分策略，这个时候外部的i是未被更新的！！！
#include&iostream&
#include&vector&
#include&cstring&
#include&stack&
struct point
char s[300];
//可能需要增大
vector&point*&
char s1[300],s2[300];
point *root=NULL;
bool find(point*p)
if(p!=root&&strcmp(p-&s,s2)==0)
point *t=p-&
int n=t-&v.end()-t-&v.begin(),i=0,j=0;
for(i=0;i&n;++i)
//不要对i重复定义,会导致错误！
if(t-&v[i]==p)
for(j=i+1;j&n;++j)
cout&&t-&v[j]-&s;
int len=p-&v.end()-p-&v.begin();
for(int k=0;k&++k)
if(find(p-&v[k]))
void Delete(point*p)
//节省内存
int i,j,n=p-&v.end()-p-&v.begin();
for(i=0;i&n;++i)
Delete(p-&v[i]);
int main()
int n,i,j;
cin.get();
while(n--)
stack&point*&
point *p1=NULL, *p2=NULL;
//森林的虚拟根
root-&father=NULL;
a.push(root);
cin.getline(s1,300);
//cin.get();
int len=strlen(s1);
if(len==0)
if(s1[0]=='{')
a.push(p2);
else if(s1[0]=='}')
//为物质名称（数据）
strcpy(p1-&s,s1);
point*t=a.top();
p1-&father=t;
t-&v.push_back(p1);
//p2用于暂时存储上一个
cin.getline(s2,300);
//遍历找匹配
if(!find(root))
cout&&&No&;
Delete(root);
cin.get();cin.get();
cin.getline(s1,300);
//关于C++几种数据读入方式的问题（已经过实验验证！）
char str[20];
//cin输入数据前会跳过空格回车TAB
//cin&&c;cout&&c;
//cin（输入数据后）遇到空格回车TAB都结束（即使要读入的是字符！!!)
// cin&&a&&c;
//cout&&a&&c;
cin&&a;//cin.get();
//cin（输入数据后）光标不会移到回车和空格和TAB后面 ，注意TAB是一个字符，只是长度相当于多个空格（数量可指定）
cin.getline(str,20);
cout&&a&&endl&&str&&
cin.getline(str,20);
//不读入回车，但光标会移到回车后面
cout&&str&&
cin&&a;cin.get();
//getline与cin.getline()光标移动情况相同
getline(cin,s);
cout&&a&&endl&&s&&
getline(cin,s);
第二道是关于树的建立与转换问题，大意是给出行走路径dud之类，要求出对应的树的深度， 以及转换为二叉树后树的深度， 首先需要根据行走路径建立树，这里采取的是数组存储方法， 每个节点用vector存储子节点表， 在此我们不需要另外用一个结构来存储转换后的二叉树，会比较麻烦，因为需要的仅仅是深度且后面用不上转换后的二叉树， 可以用传参的方式避免建树， 模拟建树过程，但是不进行存储，只是不断传参递归，求出深度即可！
Name: 树的转换
Copyright: poj
Author: xiaoli
Date: 30/10/13 11:02
Description:
1. 通过行走路径（dud之类）建立一棵树，这里给出的是用数组存储建树的方法
2. 注意多组数据必须有清空操作（初始化）， 含有STL结构时不能直接用memset!!
3. 将森林转换为二叉树并求得深度（递归），这里未建立二叉树而是直接求深度
（通过递归函数的传参可以避免结构的建立，直接求得所需的量，但这是在不需要再次用此结构的基础上！）
#include&iostream&
#include&vector&
#include&string&
//数组实现（需要用一个变量记录当前用到的数组位置，数组下标就是索引）
struct point
vector&int&
}dot[10005];
//0表示根节点
//用于不断加入元素的记录
int h1,h2;
void create_tree(int father, int pos)
//pos表示在s中的位置
if(pos&=s.length())
if(s[pos]=='d')
//新建一个节点
dot[dotpos].depth=dot[father].depth+1;
if(dot[dotpos].depth&h1)
h1=dot[dotpos].
dot[dotpos].father=
dot[father].v.push_back(dotpos);
dotpos++;
//在下一个递归前必须更新
create_tree(dotpos-1, pos+1);
else if(s[pos]=='u')
//回到父节点
create_tree(dot[father].father, pos+1);
void transfer(int father, int vpos, int depth)
//将树转换为二叉树（只求深度，不建树）
int n=dot[father].v.end()-dot[father].v.begin(),i,j;
if(depth&h2)
if(n&=vpos)
int t=dot[father].v[vpos];
transfer(t, 0, depth+1);
transfer(father, vpos+1, depth+1);
void Delete(int root)
int n=dot[root].v.end()-dot[root].v.begin(),i,j;
for(i=0;i&n;++i)
Delete(dot[root].v[i]);
dot[root].depth=0;
dot[root].father=0;
dot[root].v.clear();
int main()
int num=0,i,j;
while(cin&&s)
if(s==&#&)
num++;
dotpos=1;h1=0;h2=0;
create_tree(0,0);
transfer(0,0,0);
cout&&&Tree &&&num&&&: &&&h1&&& =& &&&h2&&
Delete(0);
//这里数组必须初始化！(不能直接用memset)
第三道是关于森林的查找， 大意是给出一堆电话号码，判断是否存在一个电话号码是另外一个的前缀， 每输入一个电话， 将其加入森林中， 从当前森林的根开始，如果找到匹配则向下，否则另外添加一个分支并将后面的数字加入， 注意存在前缀的情况有两种， 一种是遇到叶节点， 一种是待加入的这个号码已经到末尾。 一旦发现前缀情况，后面直接让输入完成即可， 不必再做处理！
这道题中需要用map优化搜索（宽度范围），分找到和找不到两种情况，需要对map的使用比较熟悉，map的使用基本方法附在这个程序后部！
Name: 电话号码
Copyright: poj
Author: xiaoli
Date: 30/10/13 11:08
Description:
1. 将输入的电话号码加入森林，加入时考虑是否有前缀重合现象（同样用数组存储，不会出现错用指针的现象）
注意确定合适的数组大小（否则会RE)，注意到每个电话号码不超过10位，所以搜索时不用担心深度的问题，
但广度上随着深度递增增加可能特别快，需要用map匹配关系方便查找（map的使用附在程序下方！）
3. 多组数据需要清空，注意递归函数中最好不要使用全局变量（尤其是在循环中！）
#include&iostream&
#include&map&
#include&string&
//虚拟根节点是0， v为空时表示叶节点
map&char,int& dot[60000]; //方便每加入一个号码时的查找
//根据号码数量上限和数字种类推出数组范围
void Delete(int root)
//用于每组测试数据结束后的清空
map&char,int&::
//不能用全局变量的迭代器（递归中前一轮会影响循环的后一个！)
for(p=dot[root].begin();p!=dot[root].end();++p)
Delete(p-&second);
dot[root].clear();
int main()
int t,n,i,j;
map&char,int&::
while(t--)
bool flag=
//未出现前缀重合
int dotpos=1;
while(n--)
//已经无需再处理
int len=s.length(),p=0;
//p表示当前树的根
for(i=0;i&=++i)
if((p!=0&&dot[p].empty())||i==len)
//重合有两种情况
it=dot[p].find(s[i]);
if(it==dot[p].end())
//没找到,则将此后的节点加入这棵树中
for(j=i;j&++j,++dotpos)
dot[p].insert(make_pair(s[j],dotpos));
//不能直接break，输入还没完成
cout&&&NO&&&
cout&&&YES&&&
Delete(0);
STL map常用操作简介
在map中插入元素
查找并获取map中的元素
从map中删除元素
2。map简介
map是一类关联式容器。它的特点是增加和删除节点对迭代器的影响很小，除了那个操作节点，对其他的节点都没有什么影响。对于迭代器来说，可以修改实值，而不能修改key。
3。map的功能
自动建立Key － value的对应。key 和 value可以是任意你需要的类型。
根据key值快速查找记录，查找的复杂度基本是Log(N)，如果有1000个记录，最多查找10次，1,000,000个记录，最多查找20次。
快速插入Key - Value 记录。
快速删除记录
根据Key 修改value记录。
遍历所有记录。
4。使用map
使用map得包含map类所在的头文件
#include &map& //注意，STL头文件没有扩展名.h
map对象是模板类，需要关键字和存储对象两个模板参数：
std:map&int, string&
这样就定义了一个用int作为索引,并拥有相关联的指向string的指针.
为了使用方便，可以对模板类进行一下类型定义，
typedef map&int, CString& UDT_MAP_INT_CSTRING;
UDT_MAP_INT_CSTRING enumM
5。在map中插入元素
改变map中的条目非常简单，因为map类已经对[]操作符进行了重载
enumMap[1] = &One&;
enumMap[2] = &Two&;
这样非常直观，但存在一个性能的问题。插入2时,先在enumMap中查找主键为2的项，没发现，然后将一个新的对象插入enumMap，键是2，值是一个空字符串，插入完成后，将字符串赋为&Two&; 该方法会将每个值都赋为缺省值，然后再赋为显示的值，如果元素是类对象，则开销比较大。我们可以用以下方法来避免开销：
enumMap.insert(map&int, CString& :: value_type(2, &Two&))
6。查找并获取map中的元素
下标操作符给出了获得一个值的最简单方法：
CString tmp = enumMap[2];
但是,只有当map中有这个键的实例时才对，否则会自动插入一个实例，值为初始化值。
我们可以使用Find()和Count()方法来发现一个键是否存在。
查找map中是否包含某个关键字条目用find()方法，传入的参数是要查找的key，在这里需要提到的是begin()和end()两个成员，分别代表map对象中第一个条目和最后一个条目，这两个数据的类型是iterator.
int nFindKey = 2;
//要查找的Key
//定义一个条目变量(实际是指针)
UDT_MAP_INT_CSTRING::iterator it= enumMap.find(nFindKey);
if(it == enumMap.end()) {
通过map对象的方法获取的iterator数据类型是一个std::pair对象，包括两个数据 iterator-&first 和 iterator-&second 分别代表关键字和存储的数据
7。从map中删除元素
移除某个map中某个条目用erase()
该成员方法的定义如下
iterator erase(iterator it); //通过一个条目对象删除
iterator erase(iterator first, iterator last);
//删除一个范围
size_type erase(const Key& key); //通过关键字删除
clear()就相当于 enumMap.erase(enumMap.begin(), enumMap.end());
接下来是最后一道，也是最难的一道， 食物链，考察的是带权并查集的使用， 说实话我开始并不知道带权并查集是啥， 所以一开始按照自己定义的数据结构和算法去做，我的想法是这样的， 将同类的划成一类， 就像并查集的基本操作那样， 否则划成不同类， 每个类的操作时均以祖先节点为主， 然后就是要满足食物链的三角循环关系， 因为被同一个类吃的必然属于同一类， 吃同一个类的必然属于同一类， A类吃B类， B类吃C类， 则C类必然吃A类； A类被B类吃， B类被C类吃， 则C类必然被A类吃。
要保证满足这个关系是很麻烦的，因为情况实在太多了，难以全部考虑， WA是意料之中， 后面不得不放弃这个想法！！！（这个想法作为失败的典例还是保留在程序的注释中了）， 这道题是借助他人的教程才弄清楚的，当然最终代码是自己写的，但算法是学来的， 带权并查集使用起来并不简单！
关于这道题， csdn网站中有别人分享的很详细的解释， 重要的是理解其原理和公式的推导，因为带权并查集的变化特别多， 可以参见我的收藏，或者直接搜那个博客
我的感悟全部集成在程序中：
Name: 食物链
Copyright: poj
Author: xiaoli
Date: 30/10/13 13:23
Description:
1.带权并查集：利用食物链中三个类型的循环捕食关系确定权值，也就是relation（与父节点的关系)
2. 同一集合中的说明关系已经确定，否则关系未定，同一集合不代表等价类，具体关系可以通过运算得到，
其中很关键的是利用食物链的三角循环这个性质， 注意不满足传递性，即A吃B，B吃C，不能得到A吃C，
反而得到的是C吃A， 也就是说， 利用A对B的关系以及B对C的关系可以运算得到A对C的关系
3. 每次节点挂载（路径压缩，合并操作）都得做关系值的更新
4. 数据结构搭建好后，重点在于关系值公式的推导！！！（运算结果模3， 同余定理）
（1）假如B对父节点A的关系是t， 则A对B的关系是（3-t)%3;
（2）假如B对A的关系是t1， C对B的关系是t2, 则C对A的关系是(t1+t2)%3；
Union操作中的关系更新公式也就是根据上面两个法则推出的，期间要用到同余定理！
注意若type（a,b)表示指令（1 或2），则type-1就表示b对a的关系！
#include&iostream&
#define MAX 50005
#define SAME 0
//与父节点类型相同
#define EATEN 1
//被父节点吃
#define EAT
//吃父节点
struct point
//食物链类型：与父节点的关系
}dot[MAX];
void Init(int n)
//初始化并查数组
for(i=1;i&=n;++i)
dot[i].father=i;
//初始化为独根树
dot[i].relation=SAME;
//自己跟自己等价，满足自洽性（很重要！！！）
//对于下面这个函数，弄清楚高度问题以及挂载关系问题！
int Find(int x)
//找到对应的父节点， 执行路径压缩后能够保证每棵树高度不超过2（根为0）
//同时更新这个节点的relation（一些操作后子节点未改变，但后面总可计算出来）
if(dot[x].father==x)
int tmp=dot[x].
dot[x].father=Find(dot[x].father);
//先更新其父节点的关系
dot[x].relation=(dot[x].relation+dot[tmp].relation)%3; //再更新自己的关系
return dot[x].
void Union(int x,int y, int a, int b, int type) //a,b分别是x,y的根节点，type指定合并类型（关系）
dot[b].father=a;
//这里确定了顺序，下面就要根据这个顺序确定关系值！
//关键是计算合并后b对a的relation
dot[b].relation=(3-dot[y].relation+type-1+dot[x].relation)%3;
int main()
int n,k,i,j;
cin&&n&&k;
int wrongnum=0, type=0,a=0,b=0;
while(k--)
cin&&type&&a&&b;
if(a&n||b&n||(type==2&&a==b))
wrongnum++;
//先找到对应的根， 再观察是否在同一个集合中
//在同一集合中说明关系已经确定(可以做判断），否则关系未确定
int t1=Find(a),t2=Find(b);
if(t1!=t2)
//在不同集合中,直接合并即可
Union(a,b,t1,t2,type);
//下面是在同一集合中的情况，不用合并，但需要分析正误!
//注意下面要直接对a,b操作，因为根都是相同的，同时高度最多为2
if(type==1)
//相等关系可以不运算直接判断
if((3-dot[b].relation+dot[a].relation)%3!=0)
wrongnum++;
else if(type==2)
if((3-dot[b].relation+dot[a].relation)%3!=2)
wrongnum++;
cout&&wrongnum&&
#include&iostream&
//这种数据结构十分麻烦， 处理起来情况太多!!!!!
//吃的关系以祖先为准
struct point
//本类的链接
//吃自己的
//自己吃的
}dot[50005];
//编号从1，注意三角循环关系
int Find(int x)
if(dot[x].father==x)
dot[x].father=Find(dot[x].father);
return dot[x].
void Union(int x, int y)
//这里传入的是每个等价类的根
dot[x].father=y;
dot[y].eat1=Find(dot[y].eat1);
dot[y].eat2=Find(dot[y].eat2);
int main()
int n,k,i,j;
cin&&n&&k;
int wrongnum=0,type=0,a=0,b=0;
for(i=1;i&=n;++i)
dot[i].father=i;
dot[i].eat1=dot[i].eat2=0;
//初始化时不存在食物关系
while(k--)
cin&&type&&a&&b;
if(type==1)
int t1=Find(a), t2=Find(b);
if(t1==t2)
if(dot[t1].eat2==t2||dot[t2].eat2==t1)
//互为捕食关系
wrongnum++;
Union(t1,t2);
else if(type==2)
if(a==b||a&n||b&n)
wrongnum++;
int t1=Find(a),t2=Find(b);
if(t1==t2||dot[t2].eat2==t1)
wrongnum++;
if(dot[t1].eat2)
//等价类已经存在
Union(t2, dot[t1].eat2);
dot[t1].eat2=t2;
if(dot[t2].eat1)
Union(t1, dot[t2].eat1);
dot[t2].eat1=t1;
int k1=Find(t1),k2=Find(t2);
if(dot[k2].eat2)
if(dot[k1].eat1)
Union(dot[k2].eat2, dot[k1].eat1);
dot[k1].eat1=dot[k2].eat2;
else if(dot[k1].eat1)
if(dot[k2].eat2)
Union(dot[k1].eat1, dot[k2].eat2);
dot[k2].eat2=dot[k1].eat1;
cout&&wrongnum&&
呵呵，昨天干掉的任务真不少， 关于森林与并查集，其实还有很多可以学的， 就必然森林的存储方式就有很多种， 但是我们一般选择自己习惯的就好， 因为一般条条大路通罗马嘛！~
总算把昨天的日记补完了！~~~
看过本文的人也看了：
我要留言技术领域：
取消收藏确定要取消收藏吗？
删除图谱提示你保存在该图谱下的知识内容也会被删除，建议你先将内容移到其他图谱中。你确定要删除知识图谱及其内容吗？
删除节点提示无法删除该知识节点，因该节点下仍保存有相关知识内容！
删除节点提示你确定要删除该知识节点吗？}