并查集相关

一、概念

并查集被很多OIer认为是最简洁而优雅的数据结构之一，主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：

• 合并（Union）：把两个不相交的集合合并为一个集合。
• 查询（Find）：查询两个元素是否在同一个集合中。

  int f[INT_MAX];//init : father[x] = x
  int find(int x){return x==f[x]?x:(f[x] = find(f[x]));}// Find function
  void merge(int x,int y){f[find(x)] = find(y);}// Merge function

  二、优化

  按秩合并

  基本思想是使包含较少结点的树德根指向包含较多结点的树的根，而这个树的大小可以抽象为树的高度，即高度小的树合并到高度大的树，这样资源利用更加合理。

    void merge(int x, int y) {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty) {
            if (rank[rootx] < rank[rooty]) {
                swap(rootx, rooty);
            }
            parent[rooty] = rootx;
            if (rank[rootx] == rank[rooty]) rank[rootx] += 1;
        }
    }

  路径压缩

  在FIND-SET操作中，把查找路径上的每个结点都直接指向根结点。路径压缩并不改变结点的秩。关于路径压缩，看图理解，之间为FIND-SET操作前集合，之后为FIND-SET操作后集合。此时，查找路径上的每一个结点都直接指向根。