一、并查集（UnionFind）：
1.定义
1.1能解决的问题
假设有一堆元素，在这些元素间可能存在一个二元、有向、可传递的关系。例如倍数关系。（S(a,b)定义为a是b的倍数，若S（a,b),S(b,c)则S（a,c）。即若a是b的倍数，b是c的倍数，则a是c的倍数）并查集（逻辑上是树形结构，可能是多个树形结构）可以通过按照元素间是否有此关系将元素划分到若干个不相交的集合中，将元素按照关系分组，判断任意两元素之间是否存在此关系，且关系若可以量化，也可以判断任意两元素间的关系的“量”是多少。
1.2并查集的操作
合并（Union）：把两个不相交的集合合并为一个集合（单个元素也可称为广义集合）。
其实是更新并查集的操作，添加一对关系，则并查集中的各个树的形状可能改变。
查询（Find）：查询两个元素是否在同一个集合中。（通过判断两个元素的parent(集合中的代表元素)是否一致）
在每一个集合中指定一个唯一的代表性元素，通过关系的传递性，将集合中其他元素与这个元素建立直接的关系（在路径压缩后才有此性质）。那么就可以通过判断两元素所在集合中的代表元素（即这个元素的parent）是否是同一个，来判断两元素是否在同一个集合中（即是否有某种关系）
2.实现
2.1最朴素的实现
public class UnionFind{
private int[] parent; //存放关系中的“父”的id
priavte double[] weight; //一对有向关系的“量”（或“值”），以“子”的下标查询 （仅仅在需要量化的关系中才需要添加这个属性。）
/**
查询操作
*/
public int find(int x){ //查找一个元素所在树的根元素（也是它最端的父元素）（也是一个元素所在集合的代表性元素）
if(parent[x]==x){
return x;
}else{
return find(parent[x])
}
}
/**
合并操作
*/
public int union(int x,int y,double weight){ //只有量化的关系才有weight参数，且weight值在合并后的变化依赖于具体的关系
//判断x,y是否在同一棵树中，如果已经在同一棵树中则不需要合并，如果不在，则让rootY做rootX的父节点，这条新增边的weight值根据从a到经过两条路的代价相等而计算出。（即x->y->rootY和x->rootX->rootY这两条路径的代价应该相等。）
father[find(x)]=find(y)
//以倍数关系为例，计算weight (不同的关系计算方式不同，不需要量化的关系不需要计算weight)
weight[find(x)]=weight*weight[y]/weight[x]
}
}
2.2优化实现-路径压缩
//路径压缩在find()方法中不仅做了“查找”这件事，还将不直接与代表元素相连的元素改成了直接与代表元素相连，修剪树高至2（注意只能从3修剪到2，因为每次find都将可能为3的地方修剪为2，所以树高没机会突破3,所以find方法不需要像之前那样递归n层），提高了查询效率。（同时需要量化的关系，weight的值在路径压缩的时候也要重新计算）find方法原来是不会修改parent里面的值的，但是修剪树，改变了树高，也改变了parent（因为改变了元素的直接父节点）
public int find(int x){
if(x!=parent[x]){ //如果还不是根节点
int origin=parent[x]; //保存其原来的父节点
parent[x]=find(parent[x]) //父节点设为根节点
weight=weight*weight[origin] //因为是递归find，所以其实find函数从根的远端开始展开，但是计算weight的值却是从近跟一端开始计算的，所以这时的weight[origin]已经是更新origin节点的父子关系（父亲已经是根节点）后的weight了,所以这步计算没毛病。
}
要注意，用union方法把并查集初始化之后，即使find方法使用的是路径压缩后的优化版本，树的形状仍然可能是高度大于2的，因为union方法合并两棵树的时候，只更改了根部的father的值，所以要等最后再调用find(a)的时候，a元素所在node才真正指向该集合的代表元素，也就是整棵树的根。如果初始化好并查集，但是没有把所有元素全部调用完一遍find的话，father数组中的father仍然可能不是总的根。如果根据father判断一共有几棵树（一共有几个集合），可能会算错。
}
3. leetcode第399题 除法求值分析
这些元素为string类型，为了方便查找，用hashMap把他们映射为int类型。
题解参考leetcode官方题解。这里贴上我的代码：
import java.util.HashMap;
import java.util.List;
import java.util.Map;
class Solution {
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
//用hashmap建立string元素和int id的对应关系
HashMap<String,Integer> hashmap=new HashMap<String,Integer>();
int id=0;
int equationSize=equations.size();
for(int i=0;i<equationSize;i++){
List<String> el=equations.get(i);
String a=el.get(0);
String b=el.get(1);
if(hashmap.get(a)==null){
hashmap.put(a,id++);
}
if(hashmap.get(b)==null){
hashmap.put(b,id++);
}
}
//新建并查集
int ufSize=hashmap.size();
UnionFind uf=new UnionFind(ufSize);
//1.初始化并查集
for(int i=0;i<equations.size();i++){
List<String> el=equations.get(i);
int x=hashmap.get(el.get(0));
int y=hashmap.get(el.get(1));
double weight=values[i];
uf.union(x,y,weight);
}
//3.查找并返回所有问题的答案
double[] ans=new double[queries.size()];
int p=0;
for(int i=0;i<queries.size();i++){
List<String> el=queries.get(i);
// String x=el.get(0);
// String y=el.get(1);
double res=0.0d;
if(hashmap.get(el.get(0))==null||hashmap.get(el.get(1))==null){
res=-1.0d;
}else{
int x=hashmap.get(el.get(0));
int y=hashmap.get(el.get(1));
res=uf.getValue(x,y);
}
ans[p++]=res;
}
return ans;
}
//建立表示并查集的内部类
private class UnionFind{
private int[] father;
private double[] weight;
//构造函数
public UnionFind(int n){
father=new int[n];
weight=new double[n];
for(int i=0;i<n;i++){
father[i]=i;
weight[i]=1;
}
}
//union
public void union(int x,int y,double weight){
//若x,y已在一个集合里了，不需要union
int rootX=find(x);
int rootY=find(y);
if(rootX==rootY){
return;
}
//如果x,y不在一个集合里，让rootY做rootX的父节点
father[rootX]=rootY;
this.weight[rootX]=weight*this.weight[y]/this.weight[x];
}
//find find是路径压缩优化后的find方法，返回的不是父节点而是“根节点”（调整后的父节点也是根节点了，当然）
public int find(int x){
if(x!=this.father[x]){ //如果节点不是根节点，则其父节点必须变为根节点，它的根节点跟它父节点的根节点一致
int origin=this.father[x]; //确定原来的直接父节点，换算weight的时候会用到
this.father[x]=find(this.father[x]);
this.weight[x]=this.weight[x]*this.weight[origin];
}
return this.father[x];
}
//getValue 判断是否是一个集合里的，返回问题的结果，无法确定或不符合要求返回-1.0
public double getValue(int x,int y){
int rootX=find(x);
int rootY=find(y);
if(rootX!=rootY){
return -1.0;
}else{
return this.weight[x]/this.weight[y];
}
}
}
}
