查集就是维护了几个动态的集合，集合中的每一个元素都标记了一个父节点，同一个集合的代表是相同的。当一个元素的父节点就是他本身时，它就是该集合的代表。

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

 

int find(int x)                  //用非递归的实现  
{  
    while (father[x] != x) x = father[x];  
    return x;  
}  
int find(int x)                   //用递归的实现  
{  
    if (father[x] != x) return find(father[x]);  
    else return x;
    //或者用return x == father[x] ? x: father[x] = find(father[x]);
}

所以，根据并查集判断两个元素是否有联系，只需判断他们是否在同一个集合里即可，也就是判断他们的代表是不是同一个

https://www.cnblogs.com/frankM/p/4399556.html

https://www.cnblogs.com/52dxer/p/10470004.html

https://www.cnblogs.com/sr1993/p/3697783.html

http://www.cnblogs.com/tanhehe/archive/2013/01/28/2883506.html

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄