基本思路O(n)

数据结构

class UF {
    // 记录连通分量
    int _count;
    // 节点 x 的父节点是 parent[x]
    vector<int> parent;

public:
    // 构造函数，n 为图的节点总数
    UF(int n) {
        // 一开始互不连通
        this->_count = n;
        // 父节点指针初始指向自己
        parent = vector<int>(n);
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

    // 其他函数
};

方法

class UF {
// 为了节约篇幅，省略上文给出的代码部分...

private:
    // 返回某个节点 x 的根节点
    int find(int x) {
        // 根节点的 parent[x] == x
        while (parent[x] != x)
            x = parent[x];
        return x;
    }

public:
    //合并树
    void union_(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;
        // 将两棵树合并为一棵
        parent[rootP] = rootQ;
        // parent[rootQ] = rootP 也一样

        // 两个分量合二为一
        _count--;
    }
    // 返回当前的连通分量个数
    int count() {
        return _count;
    }


    //判断是否为连通分量
    bool connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }
};

三、平衡性优化 O(1)

上面这种解法，find , union , connected 的时间复杂度都是 O(N)。这个复杂度很不理想的,诸如社交网络这样数据规模巨大的问题，对于 union 和 connected 的调用非常频繁，每次调用需要线性时间完全不可忍受。

我们其实是希望，小一些的树接到大一些的树下面，这样就能避免头重脚轻，更平衡一些。 结构（新增重量）：

class UF {
private:
    int _count;
    vector<int> parent;
    // 新增一个数组记录树的“重量”
    vector<int> size;

public:
    UF(int n) {
        this->_count = n;
            this->parent.resize(n);
        // 最初每棵树只有一个节点
        // 重量应该初始化 1
        this->size.resize(n); 
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
    // 其他函数
};

修改union方法：

class UF {
private:
    // 为了节约篇幅，省略上文给出的代码部分...

public:
    void union_(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;

        // 小树接到大树下面，较平衡
        if (size[rootP] > size[rootQ]) {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        } else {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
        _count--;
    }
};

四、路径压缩

这步优化虽然代码很简单，但原理非常巧妙。

其实我们并不在乎每棵树的结构长什么样，只在乎根节点。

因为无论树长啥样，树上的每个节点的根节点都是相同的，所以能不能进一步压缩每棵树的高度，使树高始终保持为常数？ 这样每个节点的父节点就是整棵树的根节点，find 就能以 O(1) 的时间找到某一节点的根节点，相应的，connected 和 union 复杂度都下降为 O(1)。

1.find加一行代码

class UF {
    // 为了节约篇幅，省略上文给出的代码部分...

private:
    int find(int x) {
        while (parent[x] != x) {
            // 这行代码进行路径压缩
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
};

2.递归find(效率更高)

压缩更彻底，完全压平树枝

class UF {
    // 为了节约篇幅，省略上文给出的代码部分...

    // 第二种路径压缩的 find 方法
    public:
        int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
};