【lazy标记得思想】HDU3635 详细学习并查集

部分内容摘自以下大佬的博客，感谢他们！

http://blog.csdn.net/dm_vincent/article/details/7769159

http://blog.csdn.net/dm_vincent/article/details/7655764

基础得可以去看上面的连接，再此我只记录一些温故而知新得知识点

并查集，连通起来后类似一颗颗得树，我们得基本操作是Find函数，寻找树根，所以树得高度，成为了，并查集算法快不快的关键条件，为了加快算法，我们采取以下操作：

1.尽可能得让每一个结点直接连到树根（过程中优化）

int Find(int x)

{

    while(x != pre[x])

    {

        pre[x] = pre[pre[x]];

        x = pre[x];

    }

    return x;

}

2.进行树得合并得时候，避免造成畸形数目

void join(int a,int b)

{

    int u = Find(a);

    int v = Find(b);

    if(u != v)

    {

        if(s[u] > s[v])

        {

            pre[v] = u;

            s[u] += s[v];

        }

        else

        {

            pre[u] = v;

            s[v] += s[u];

        }

    }

}

这里用到了s数组记录的是这个树得大小，一开始初始化都为1，更新只需要再连树得时候进行

我觉得以下这个理解或者应用，让我更加理解了并查集得数据结构，以及解决问题时得建模思考方向

对这个问题抽象之后，就是要求进行若干次union操作之后，还会剩下多少颗树(或者说还剩下多少Connected Components)。反映到这个例子中，就是要求有多少“圈子”。其实，这也是社交网络中的最基本的功能，每次系统向你推荐的那些好友一般而言，会跟你在一个“圈子”里面，换言之，也就是你可能认识的人，以并查集的视角来看这层关系，就是你们挂在同一颗树上。

HDU3635_不错的一道题目

题目大意：

题意：起初球i是被放在i号城市的，在年代更迭，世事变迁的情况下，球被转移了，而且转移的时候，连带该城市的所有球都被移动了：T A B（A球所在的城市的所有球都被移动到了B球所在的城市），Q A（问：A球在那城市？A球所在城市有多少个球呢？A球被转移了多少次呢？）

(上面题意的描述摘自：http://www.cnblogs.com/Shirlies/archive/2012/03/06/2382118.html)

不错得一道题目，按照我们原来的并查集优化来想，前两个输出都比较简单，就是次数问题

（ps：当然了，根据题意，我们时不能进行平衡树得保持得，因为最终状态（树根）是确定得）

对于次数：第一个跟新得地方肯定是join函数里面，比较容易想到的时一旦合并，就使每一个合并的元素++，这样的话会超时，只能优化，有点类似线段树中得lazy标记，我们不能一更到底，那就先更新最上层，然后想办法传递给下层，如和传递呢，好像我们还有Find函数

在Find函数中，我们会进行路径压缩，这很好，因为保证了，tm【x】相加得唯一性，这时候要稍微改变以下Find函数，因为我要传递得值以前是根，现在不是了所以我要后退一步，就是从判断x是不是根后退到判断pre【x】是不是根，然后进行tm【x】得更新优化，一旦优化完毕我们就进行路径压缩，防止合并多次。虽然有了路径压缩，但是最后我们还是要进行一次Find（a），才能进行后续得输出。

不错的一道题目，

#include <iostream>

#include <string.h>

#include <cstdio>

using namespace std;

const int maxn = 1e6+1e3;

int pre[maxn];

int s[maxn];

int tm[maxn];

int Find(int x)

{

    //路径压缩

    while(pre[x] != pre[pre[x]])

    {

        tm[x] += tm[pre[x]];

        pre[x] = pre[pre[x]];//路径压缩！！非常棒！！！

    }

    return pre[x];

}

void join(int a,int b)

{

    int u = Find(a);

    int v = Find(b);

    if(u != v)

    {

        pre[u] = v;

        tm[u]++;

        s[v] += s[u];

    }

}

void init(int n)

{

    for(int i = 0;i <= n;i++)

    {

        pre[i] = i;

        s[i] = 1;

        tm[i] = 0;

    }

}

int main()

{

    char c;

    int t,a,b,n,m;

    scanf("%d",&t);getchar();

    int cas = 1;

    while(t--)

    {

        scanf("%d %d",&n,&m);getchar();

        init(n);

        printf("Case %d:\n",cas++);

        while(m--)

        {

            scanf("%c",&c);

            if(c == 'T')

            {

                scanf("%d %d",&a,&b);getchar();

                join(a,b);

            }

            else

            {

                scanf("%d",&a);getchar();

                int ans = Find(a);

                printf("%d %d %d\n",ans,s[ans],tm[a]);

                printf("%d   &&    \n",pre[a]);

            }

        }

    }

    return 0;

}

巴特西

【lazy标记得思想】HDU3635 详细学习并查集

最新文章

热门文章