不相交集

1.解决等价问题的一种数据结构，数据结构实现简单

等价问题：R表示某种关系 1.自反性 aRa=a 2.对称性： aRb=bRa 3.传递性例如：两个城市在同一个国家表明两个城市明显等价

集合中任意元素独一无二的，Si与Sj集合之间操作通过 union与find算法

在集合：将所有数据采用数组表示，数组下标表示该元素，数组内表示该元素的父结点，root数组值负值表示该树包含元素或者该树的高度

Union 集合合并时候按照两种不同方式进行合并：按照树的大小进行合并 2.按照树的高度进行Union

1.树按照大小进行合并，集合元素小向集合元素大的方向进行合并，缺点Union合并相等大小的树时候会得到斜树：

 1 public void union (int root1,int root2)
 2     {
 3         /*按照树大小进行合并*/
 4         if(s[root2]<s[root1])/*root2 is deeper*/
 5         {
 6             s[root1]=root2;
 7             /*更新元素量*/
 8             s[root2]=s[root1]+s[root2];
 9         }
10         
11         else
12         {
13             if(s[root1]==s[root2])
14             {
15                 if(root1<root2)/* is equally choose 下标更小成为root*/
16                     s[root2]=root1;
17                 else
18                     s[root1]=root2;
19             }
20             else{
21                  
22                 s[root2]=root1;
23             }
24             s[root1]=s[root1]+s[root2];
25         }
26     }

2.按照树的高度进行合并时候：只有相等高度的树才能让树的高度增1

public void union1 (int root1,int root2)
    {
        /*按照树大小进行合并*/
        if(s[root2]<s[root1])/*root2 is deeper*/
        {
            s[root1]=root2;
            /*更新元素量*/
            s[root2]=s[root1]+s[root2];
        }
        
        else
        {
            if(s[root1]==s[root2])
            {
                s[root1]--;
            }
            
                 
                s[root2]=root1;
            
        }
    }