并查集算法分析

并查集算法

一、并查集能解决哪类问题

1. 前提条件
   • 如果A与B有关系，B与C也有关系，那么，A与C就有关系；
   • 举例：在下图中，A与B是连通的，B与C也是连通的，那么显然，A与C就是连通的。我们把A,B,C称之为节点。
2. 问题描述
   • 在下列群节点中，已知一些节点之间的关系情况现在给出任意两个节点x和y，判断x和y是否有关系？这些节点中共有多少个独立的群体？

二、怎样解决

1. 解决思路
   • 每个群体推选出一个根节点；
   • 两个节点是否在一个群体中，只需要判断它们的根节点是否相同；
   • 有多少个根节点就有多少个群体。
2. 实现方法（C/C++语言实现）
   • 初始化

     const int max=10000;//max为定义的最大节数
     int pre[max];//max为定义的最大节数
     void init(){//初始化，每个节点都是根节点
     	for(int i=0;i<max;i++)
     		pre[i]=i;
     }
                

   • 寻找根节点

     int find(int node){
     	while(pre[node]!=node)
     		node=pre[node];
     	return node;
     }
                

   • 并为一个集合

     void join(int node1,int node2){
     	node1=find(node1);
         node2=find(node2);
         if(node1!=node2)//判断两个节点x,y是否有联系
             pre[node1]=node2;
     }
                

三、例题

• L 2 − 010 L2-010 L2−010排座位
• L 2 − 024 L2-024 L2−024部落
• L 2 − 007 L2-007 L2−007家庭房