并查集—两种压缩路径的比较

题目：http://www.fjutacm.com/Problem.jsp?pid=2144

两种最后的 ac 时间差不多

两种压缩路径的比较

一，是通过用 rank 数组，记录树的深度直接比较

二，直接让所有点指向 根，但他压缩路径会延迟一下（具体可以画一下图，或者我在另外一篇有讲到 https://www.cnblogs.com/asdfknjhu/p/12528457.html ）

如果增加的边始终只有一个是新的，其实应该也差不了多少（其实在时间复杂度上我也不太会算）

一 的深度只有当两个集合的深度不一样时才不会增加

二 的深度始终为 1，

所以，应该说，二 路径是不完全压缩，或者说压缩的还不够　　一  的路径压缩会延迟

一，

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define M(a,w) memset(a,w,sizeof(a));
#define N (int)1e6+6
int pa[N], max[N], num[N], rank[N];
int maxer(int x, int y)
{
    return x > y ? x : y;
}
int find(int x)
{
    while (pa[x] != -1)
        x = pa[x];
    return x;
}
int join(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y)
        return 0;
    if (rank[x] > rank[y])
    {
        pa[y] = x;
        num[x] += num[y];
        max[x] = maxer(max[x], max[y]);
    }
    else if (rank[x] < rank[y])
    {
        pa[x] = y;
        num[y] += num[x];
        max[y] = maxer(max[x], max[y]);
    }
    else
    {
        pa[y] = x;
        num[x] += num[y];    // 累加
        max[x] = maxer(max[x], max[y]);   // 找到目前编号
        rank[x]++;
    }
    return 1;
}
int main(void)
{
    int n, m;
    char s[10];
    while (scanf("%d%d", &n, &m) != EOF)
    {
        M(pa, -1); M(rank, 0);
        for (int i = 1; i <= n; i++)
        {
            max[i] = i;
            num[i] = 1;
        }

        int sum = n, x, y;
        while (m--)
        {
            scanf("%s", s);
            if (s[0] == 'u')
            {
                scanf("%d%d", &x, &y);
                if (join(x,y)==1)
                {
                    sum--;
                }
            }
            if (s[0] == 's'&&s[1] == 'a')
            {
                scanf("%d%d", &x, &y);
                if (find(x) == find(y))
                    puts("1");
                else
                    puts("0");
            }
            if (s[0] == 'n')
            {
                scanf("%d", &x);
                printf("%d
", num[find(x)]);
            }
            if (s[0] == 'm')
            {
                scanf("%d", &x);
                printf("%d
", max[find(x)]);
            }
            if (s[1] == 'e')
            {
                printf("%d
", sum);
            }

        }

    }
}

二，

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define M(a,w) memset(a,w,sizeof(a));
#define N (int)1e6+6
int pa[N], max[N], num[N];
int maxer(int x, int y)
{
    return x > y ? x : y;
}
int find(int x)
{
    int p = x;
    while (x != pa[x])
        x = pa[x];
    while (p != x)   // 让所有点都直接指向 根
    {
        int t = pa[p];
        pa[p] = x;
        p = t;
    }
    return x;
}
void join(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y)
        return;

    // 所以最后都是两层的就不用比较了吗
    pa[x] = y;
    max[y] = maxer(max[x], max[y]);
    num[y] += num[x];
}
int main(void)
{
    int n, m;
    char s[10];
    while (scanf("%d%d", &n, &m) != EOF)
    {
        for (int i = 1; i <= n; i++)
        {
            pa[i] = i;
            max[i] = i;
            num[i] = 1;
        }

        int sum = n, x, y;
        while (m--)
        {
            scanf(" %s", s);
            if (s[0] == 'u')
            {
                scanf("%d%d", &x, &y);
                if (find(x) != find(y))
                {
                    join(x, y);
                    sum--;
                }
            }
            if (s[0] == 's'&&s[1] == 'a')
            {
                scanf("%d%d", &x, &y);
                if (find(x) == find(y))
                    puts("1");
                else
                    puts("0");
            }
            if (s[0] == 'n')
            {
                scanf("%d", &x);
                printf("%d
", num[find(x)]);
            }
            if (s[0] == 'm')
            {
                scanf("%d", &x);
                printf("%d
", max[find(x)]);
            }
            if (s[1] == 'e')
            {
                printf("%d
", sum);
            }

        }
    }
}

======== ======= ======= ======= ====== ===== ===== === == =

.我的朋友，我还有一点疑虑——你是不是因为太懦弱了，才这样以炫耀自己的痛苦来作为自己的骄傲？ 

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 -- 《基督山伯爵》

My friend, I have a little doubt -- are you too weak to show off your pain as a source of pride?

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 --    ”The count of monte cristo“