对于n个集合来说，如果把它们依次合并的时间复杂度是O(n^2)，如下：

第一次合并只需要1个，第二个要合并2个，后面3个4个。。。。
这样1+2+3+….+n，所以耗费的时间复杂度为O(n^2)

对于启发式合并来讲，时间复杂度可以降低到O(nlogn)，思想是每次合并，让集合元素少的那个向多的一方合并。
证明如下：
考虑每个元素对于合并复杂度的贡献，按照集合元素少的向多的一方合并，找到合并次数最多的元素（应该是集合元素个数最少的那个集合），此时看这个集合中某一个元素e，他在合并到别的集合中时，那集合元素个数至少翻一倍，每次合并最少翻一倍的情况，那这个元素e最多合并logN次，他的贡献就是logN，一共n个元素，所以最终复杂度为O(nlogn)。

ps：如果想不明白可能和我思路卡在一个位置，就是下面这句话：他在合并到别的集合中时，那集合元素个数至少翻一倍，每次合并最少翻一倍的情况，那这个元素e最多合并logN次我在想的时候认为每次都把少的向大的合并，那如果每次都向第一个集合合并岂不是要N次，怎么会是logN呢。这里要注意的是贡献值是元素e合并了多少次，看N^2的暴力做法，就是一号点被合并了多少次，那就都是他合并到了别的集合中。而每次都向第一个集合合并，很显然除了第一次其余的合并都不能算是元素e的贡献。

例题：

1. 梦幻布丁

题目大意：给定n个数字，每个数字代表一个颜色，有两种操作：

每次操作把所有颜色为X的变成Y
查询有多少段颜色，连续相同的算作一段

思路：
暴力做法复杂度很明显每次扫描一遍，M次操作，因此复杂度为O(nm)，大概在1e10左右。
把一种颜色全部变成另一种颜色想成把X的所有数字全部合并到Y里面去。最终的结果一定是所有的都变成一个颜色（都在一个集合中）。根据上面的启发式合并思想，复杂度降低为O(NlogN)。

具体写法：

查询直接输出即可，最开始直接扫描一遍段数就出来了
当把X变成Y时，如果X的个数比Y多，就要反过来把Y合并到X中（可以映射一下颜色，比如1和2开始代表的颜色是1和2，当要把1合并到2中，但是发现应该2合并到1更好，那只需要让1代表2，2代表1就行了）。如果X的个数比Y少就正常合并即可
可以维护一个邻接表，（现在假设X要合并到Y中），那么遍历颜色为X的链表，判断每个点的前后是不是颜色Y，如果是Y，那么段数-1。然后改变X的颜色，把X的那个链表用尾插法放到Y中
这里可以证明一开始段数是最多的，因为如果让段数变多，必然需要有某一段之中原来颜色相同，现在颜色不同，这很显然不可能，一个颜色要变全变的。
剩下的看代码吧，有注释。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = 1000010;
int seg;
int n, m;
int h[M], e[N], ne[N], idx;
int color[N], sz[M], p[M];
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
    sz[a] ++ ; // 记录当前颜色有多少个（当前集合有多少个点）
}
void merge(int& x, int& y) { // 注意这里的引用啊！！
    if (x == y) return;
    if (sz[x] > sz[y]) swap(x, y); // 映射真实颜色
    for (int i = h[x]; ~i; i = ne[i]) {
        int j = e[i];
        seg -= (color[j - 1] == y) + (color[j + 1] == y); // 如果前面的点和要变成的点一样，那段数就会减一，后面也一样
    }
    for (int i = h[x]; ~i; i = ne[i]) {
        int j = e[i];
        // 这里为什么不和上面一起写呢？画个图就知道了，连续的一段会多减一部分
        color[j] = y;
        if (ne[i] == -1) { // 尾插，先让x的尾巴连上y的头，然后y的头换成x的头
            ne[i] = h[y], h[y] = h[x];
            break;
        }
    }
    h[x] = -1;
    sz[y] += sz[x], sz[x] = 0; // 记录当前集合个数，很重要啊！！按它合并的
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) {
        scanf("%d", &color[i]);
        add(color[i], i);
        if (color[i] != color[i - 1]) seg ++ ; // 记录段数
    }
    // 映射颜色，一开始颜色都是自己对应自己，但是如果要反过来合并，颜色直接调换即可
    for (int i = 0; i < M; i ++ ) p[i] = i; 
    while (m -- ) {
        int op, a, b;
        scanf("%d", &op);
        if (op == 2) printf("%d\n", seg);
        else {
            scanf("%d%d", &a, &b);
            // 这里要按实际颜色合并
            merge(p[a], p[b]);
        }
    }
    return 0;
}