聊聊并查集（一）

并查集

星期五花了一个小时敲完了并查集代码，花了大部分时间去调试结果发现问题源头出在eclipse重定向中与我自身代码并无关系，最后只能命令行运行了。

并查集可能这个名字很多人很陌生，其实我本身也是今天第一次听到这个概念，其中有几个专有名词分别是：触点、连接、等价类、连通分量。可能这么说太抽象了，我拿具体的例子来举个例：

金庸写的小说中肯定有正邪两派之分，那么其中一个一个人物我们称之为触点，那么为了不与同道中人发生打斗，比如乔峰和段誉这无论如何打不起来，因为他们是拜把子兄弟。那么他们的拜把子兄弟这个关系就是连接的意思。
那么怎么等价类怎么理解呢？

• 自反性：乔峰和乔峰自己是相连的(自己肯定跟自己有关系，为了找出带头大哥也是为了自己崇高理想信念)
• 对称性：乔峰和段誉有关系，那么段誉与乔峰有关系。
• 传递性：乔峰和段誉有关系，段誉与虚竹也有关系，那么乔峰与虚竹也有关系。

最后这三个人形成的关系网算是一个连通分量（当然这是直接与乔峰有关系）,比如梦姑肯定与虚竹有关系，所以梦姑不可能跟乔峰为敌，她也处在这个关系网内。如果我加上阿紫可能关系会乱类似于这种情况先排除。

那么我们来扯扯快乐的单身汉鸠摩智，鸠摩智他就是一个人，他前期与段誉为敌，那么基本算是跟那个连通分量为敌，乔峰看见不降龙十八掌打死他（竟敢欺负我兄弟，虽然我不屑于跟你纠缠）

按以上规律我们可以用代码表示

public class UF{
    private int[] ids;
    private int count;
    public UF(int n) {
        count = n;
        ids = new int[n];
        for(int i=0; i<n; i++) {
            ids[i]=i;//为了简单都是从0到n的
        }
    }
    public int getCount() {
        return count;
    }
    public int find(int p) {
        return ids[p];
    }
    public boolean connect(int p, int q) {
        return find(p) == find(q);
    }
    public void union(int p, int q) {
        int pid = find(p);
        int qid = find(q);
        for(int i=0;i<ids.length;i++) {
            if(pid==ids[i]) ids[i] = qid; 
        }
        count--;
    }
}

ids数组下标作为唯一区分人物的id，那么数组值代表他们那一个门派的代表人物比如说乔峰是1号那么ids[虚竹.id]=1，ids[段誉.id]=1；(只是个简略版本后期会优化)；
count代表不同派系比如慕容复有自己一派系、乔峰有自己一个派系、鸠摩智快乐的单身汉一派系。我们怎么输入呢？数组大小代表有几个人，然后通过每一对之间是否有关系组成各个派系。（大家可以试一试）