小雷的冰茶几——并查集

迷南。 2022-09-29 05:21 110阅读 0赞

think:  
1并查集部分基本知识包括三个过程即可由三个函数来完成，第一是初始化过程，第二是查找过程，第三是合并分元素过程  
2初始化过程中默认每一个分元素的Boss元素是其本身  
3查找过程可以有递推思想完成，也可由递归思想完成，尽量使用递推方法，递推方法可以减少查找时间而且不用担心递归可能会造成栈溢出的问题  
4合并分元素的过程其实就是分别寻找两个分元素的Boss元素，然后直接将Boss元素合并

5参考——百度百科如下

主要操作
    编辑
    初始化
    把每个点所在集合初始化为其自身。
    通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度均为O(N)。
    查找
    查找元素所在的集合，即根节点。
    合并
    将两个元素所在的集合合并为一个集合。
    通常来说，合并之前，应先判断两个元素是否属于同一集合，这可用上面的“查找”操作实现。

小雷的冰茶几  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
小雷有个特殊的癖好，平时喜欢收藏各种稀奇古怪的东西，譬如。。。。,还有。。。。，也包括。。。。。小雷是一个喜欢分享的童鞋，这次小雷又给大家带来一套神奇的东西，那就是举世无双的冰茶几！  
顾名思义，这些茶几被冰冻住了，最主要的是他们是易碎品，毕竟被冻住了。因此小雷要很小心翼翼的移动他们。一些茶几是冻在一起的，因此一套冰茶几分为好几部分，并且如果茶几A与B冻在一起，B与C冻在一起，那么A与C也就冻在了，即冰冻状态有传递性，ABC此时会看作一个整体。  
为了保证冰茶几的完整性，小雷每次只能移动一整块冰茶几，也就是冰冻在一起的一部分。小雷想知道他需要搬几次才能全部搬到实验室，你能帮小雷快速计算出答案么？

Input  
多组输入，先输入组数T（1 < = T < = 200）。  
对于每组输入，先输入一个整数n（1 < = n < = 100000），k（0 < = k < = 100000），茶几编号1~n。  
之后k行，每行两数x，y（1 < = x，y < = n），表示第x个茶几和第y个茶几冰冻在一起。

Output  
对于每组输入，先输出”Case z: ”（不带引号）表示组数，再输出一个整数，表示小雷需要搬动的次数。

Example Input  
3  
3 1  
1 2  
5 2  
1 2  
3 4  
5 2  
1 2  
2 3

Example Output  
Case 1: 2  
Case 2: 3  
Case 3: 3

Hint

Author  
2015年第五届ACM趣味编程循环赛(第一场) by LeiQ

以下为accepted代码

#include <stdio.h>
    int ans[100004];
    void Init(int n)//初始化待查集合
    {
        for(int i = 1; i <= n; i++)
            ans[i] = i;
    }
    int Getf(int v)//寻找当前元素的Boss
    {
        while(v != ans[v])
        {
            v = ans[v];
        }
        return v;
    }
    void Merge(int u, int v)//合并两个分元素
    {
        int t1 = Getf(u);
        int t2 = Getf(v);
        if(t1 != t2)
            ans[t1] = t2;
    }
    int main()
    {
        int T, n, k, i, j, cnt, u, v;
        scanf("%d", &T);
        for(i = 1; i <= T; i++)
        {
            cnt = 0;
            scanf("%d %d", &n, &k);
            Init(n);
            for(j = 0; j < k; j++)
            {
                scanf("%d %d", &u, &v);
                Merge(u, v);
            }
            for(j = 1; j <= n; j++)
            {
                if(ans[j] == j)
                    cnt++;
            }
            printf("Case %d: %d\n", i, cnt);
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 104ms
    Take Memory: 500KB
    Submit time: 2017-03-14 20:09:47
    ****************************************************/

以下为time limit exceeded代码——原因：重复查询

#include <stdio.h>
    int ans[100004];
    void Init(int n)//初始化待查集合
    {
        for(int i = 1; i <= n; i++)
            ans[i] = i;
    }
    int Getf(int v)//寻找当前元素的Boss
    {
        while(v != ans[v])
        {
            v = ans[v];
        }
        return v;
    }
    void Merge(int u, int v)//合并两个分元素
    {
        int t1 = Getf(u);
        int t2 = Getf(v);
        if(t1 != t2)
            ans[t1] = t2;
    }
    int main()
    {
        int T, n, k, i, j, u, v, cnt;
        scanf("%d", &T);
        for(i = 1; i <= T; i++)
        {
            cnt = 0;
            scanf("%d %d", &n, &k);
            Init(n);//初始化待查集合
            for(j = 0; j < k; j++)
            {
                scanf("%d %d", &u, &v);
                Merge(u, v);//合并
            }
            for(j = 1; j <= n; j++)
            {
                if(Getf(j) == j)//超时原因
                    cnt++;
            }
            printf("Case %d: %d\n", i, cnt);
        }
        return 0;
    }
    
    /***************************************************
    User name: 
    Result: Time Limit Exceeded
    Take time: 1010ms
    Take Memory: 0KB
    Submit time: 2017-03-14 20:00:06
    ****************************************************/