并查集

在一些有 N 个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内竞赛题中，其特点是看似并不复杂，但数据量极大，若用传统的线性表等数据结构来描述的话，往往超过了空间的限制；即使在空间上能勉强通过，运行的时间复杂度也极高，根本不可能在比赛规定的运行时间内计算出试题需要的结果，只能采用一种特殊数据结构——并查集来描述。
一、数学准备
首先，我们从数学的角度给出等价关系的定义：
定义：如果集合 S 中的关系 R 是自反的，对称的，传递的，则称它为一个等价关系。
—自反：x＝x；
—对称：若 x＝y，则 y＝x；
—传递：若 x＝y、y＝z，则 x＝z。
要求：x、y、z 必须要同一个全集中。
〖程序清单〗 （1）并查集的数据定义：int father[maxn]; （2）初始化： for（int i=1; i<=n; i++） father[i]=i; 因为每个元素属于单独的一个集合，所以每个元素以自己作为根结点。 （3）寻找根结点编号并压缩路径：

int root(int v) // 获取父亲/根元素
{
  if (father[v]!=v) father[v]= getfather(father[v]);
  return father[v];
  return father[v] == v ? v : father[v] = root(father[v]);
}
（4）合并两个集合：
void union(int x, int y)
{
  x= root(x);
  y= root(y);
  root[x]=y;
}
（5）判断元素是否属于同一结合：
bool judge(int x, int y:)
{
  x= root(x);
  y= root(y);
  if (x==y) return true;
      else return false;
}
这个的引题已经完全阐述了并查集的基本操作和作用。
int main(){
  cin>> n>> m>> p;
  for（int i=1; i<=n; i++） father[i]=i; //初始化
  for(int i=1; i<=m; i++){
    cin>> ai>> bi;
    union(ai, bi); 
    }
  for (int i=1; i<=p; i++){
    cin>> pi1>> pi2;
    if (judge(pi1, pi2)) 
      cout<<”Yes”<<endl;
    else cout<<”No”<< endl;
    }
  return 0;
}