专栏首页机器学习与自然语言处理04-树5. File Transfer--并查集

04-树5. File Transfer--并查集

  对于一个集合常见的操作有:判断一个元素是否属于一个集合;合并两个集合等等。而并查集是处理一些不相交集合(Disjoint Sets)的合并及查询问题的有利工具。

并查集是利用树结构实现的。一个集合用一棵树来表示,而多个集合便是森林。并查集中的“并”是将两个集合合并即两棵树合并成一颗树;“查”是查找一个元素属于哪个集合,即查找一个节点属于哪棵树。思路如下:

  • 查:通过节点找寻父节点,一直向上查找直到根节点,返回根节点,而根节点代表唯一的那棵树;
  • 并:先查找到两个节点所在的树,如果在同一棵树中(即查找到的根节点相同),则直接返回;否则将一棵树作为子树连到另一棵树上,即将一个根节点作为另一个根节点的儿子。

  那么问题来了,应该将哪个根节点作为儿子呢?简单的想法是随便都可以,所以在编程实现中,要么一直让前一个根节点作为儿子,要么一直让后一个根节点作为儿子。这种实现的优点是实现简单,代码简洁短小。但是要知道相对短的代码不一定效率高。在这个问题上,这种做法容易让树失去平衡,因为可能会将较大树作为较小树的子树,使树的深度增大。事实上,更自然的想法是将较小树作为较大树的子树,这样合并操作不会增加树的深度(当然如果两棵树同样大一定会增加),使树相对平衡。

集合没有精确定义,通常把一些互不相同的东西放在一起所形成的整体就叫做集合。至于为什么放在一起,是根据具体问题的需求,比如把有公路相连的城镇放在一个集合中(连通性问题)。确定性,互异性,无序性是集合的三大性质。由于集合的性质,通常可以和自然数一一对应。因此,用数组实现并查集非常方便且巧妙:数组下标(从1开始)作为树节点,数组下标对应的值作为父节点。由于根节点没有父节点,故不妨令它对应数组的值为非正数。而如何比较两棵树谁大谁小,一个非常巧妙的技巧是让根节点对应的数组的值(非正数)的绝对值作为这棵树的深度。这样做代码不仅简洁,而且节省空间。具体实现的代码如下:

int father[N] = {0};      //初始化,所有节点都是根节点,深度为0;N为最大可能节点数
int n;                         //n为实际节点数
/*查找函数*/
int Find(int father[], int n, int x)
{
    int root;
    for (root = x; father[root] > 0; root = father[root]);  //向上遍历直到根节点退出循环
    return root;    //返回根节点
}
/*合并函数*/
void Union(int father[], int n, int a, int b)
{
    int ARoot, BRoot;
    ARoot = Find(father, n, a);    //找到a节点所在树的根节点
    BRoot = Find(father, n, b);    //找到b节点所在树的根节点
    if (ARoot == BRoot)
        return;
    else if (father[ARoot] > father[BRoot]) //B树深度大于A树
    {
        /*树的深度不变*/
        father[ARoot] = BRoot;              //将A树指向B树
    }
    else
    {
        if (father[ARoot] == father[BRoot])//A,B两棵树深度相同
            father[ARoot]--;    //树的深度加1,根节点对应数组的值(非正数)的绝对值为这棵树的深度
        father[BRoot] = ARoot;
    }
}

 下面是一个考察并查集的练习,题目来源:http://www.patest.cn/contests/mooc-ds/04-%E6%A0%915

We have a network of computers and a list of bi-directional connections. Each of these connections allows a file transfer from one computer to another. Is it possible to send a file from any computer on the network to any other?

Input Specification:

Each input file contains one test case. For each test case, the first line contains N (2<=N<=104), the total number of computers in a network. Each computer in the network is then represented by a positive integer between 1 and N. Then in the following lines, the input is given in the format:

I c1 c2  

where I stands for inputting a connection between c1 and c2; or

C c1 c2    

where C stands for checking if it is possible to transfer files between c1 and c2; or

S

where S stands for stopping this case.

Output Specification:

For each C case, print in one line the word "yes" or "no" if it is possible or impossible to transfer files between c1 and c2, respectively. At the end of each case, print in one line "The network is connected." if there is a path between any pair of computers; or "There are k components." where k is the number of connected components in this network.

Sample Input 1:

5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
S

Sample Output 1:

no
no
yes
There are 2 components.

Sample Input 2:

5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
I 1 3
C 1 5
S

Sample Output 2:

no
no
yes
yes
The network is connected.代码如下:
#include <cstdio>
#include <cstring>

#define N 10010

/*查找函数: 通过节点的值查找其所在树的根节点*/
int Find(int father[], int n, int x);
/*合并函数: 合并两个节点*/
void Union(int father[], int n, int a, int b);

int main()
{
    char operation[10];
    int father[N] = {0};      //初始化,所有节点都是根节点,深度为0
    int n;
    int a, b;

    scanf("%d", &n);
    while (scanf("%s", operation) == 1)
    {
        if (strcmp(operation, "S") == 0) break;
        if (strcmp(operation, "C") == 0)
        {
            scanf("%d%d", &a, &b);
            if (Find(father, n, a) == Find(father, n, b)) //若根节点相同则在同一颗树上
                printf("yes\n");
            else
                printf("no\n");
        }
        else
        {
            scanf("%d%d", &a, &b);
            Union(father, n, a, b);
        }
    }

    int k = 0;      //统计根节点的个数(树的个数)
    for (int i = 1; i <= n; i++)
    {
        if (father[i] <= 0)
            k++;
    }
    if (k == 1)     //只有一棵树,即全部连通
        printf("The network is connected.\n");
    else
        printf("There are %d components.\n", k);

    return 0;
}

void Union(int father[], int n, int a, int b)
{
    int ARoot, BRoot;
    ARoot = Find(father, n, a);    //找到a节点所在树的根节点
    BRoot = Find(father, n, b);    //找到b节点所在树的根节点
    if (ARoot == BRoot)
        return;
    else if (father[ARoot] > father[BRoot]) //B树深度大于A树
    {
        /*树的深度不变*/
        father[ARoot] = BRoot;              //将A树指向B树
    }
    else
    {
        if (father[ARoot] == father[BRoot]) //两树深度相等
            father[ARoot]--;    //树的深度加1,根节点对应数组的值(非正数)的绝对值为这棵树的深度
        father[BRoot] = ARoot;
    }
}

int Find(int father[], int n, int x)
{
    int root;
    for (root = x; father[root] > 0; root = father[root]);  //向上遍历直到根节点退出循环
    return root;    //返回根节点
}

 图解样例2如下:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 04-树6. Huffman Codes--优先队列(堆)在哈夫曼树与哈夫曼编码上的应用

    题目来源:http://www.patest.cn/contests/mooc-ds/04-%E6%A0%916 In 1953, David A. Huffm...

    llhthinker
  • POJ2488-A Knight's Journey(DFS+回溯)

    题目链接:http://poj.org/problem?id=2488 A Knight's Journey Time Limit: 1000MS ...

    llhthinker
  • 二叉树的遍历:先序中序后序遍历的递归与非递归实现及层序遍历

      对于一种数据结构而言,遍历是常见操作。二叉树是一种基本的数据结构,是一种每个节点的儿子数目都不多于2的树。二叉树的节点声明如下: 1 typedef str...

    llhthinker
  • 并查集Union-find及其在最小生成树中的应用

    并查集是一种用途广泛的数据结构,能够快速地处理集合的合并和查询问题,并且实现起来非常方便,在很多场合中都有着非常巧妙的应用,。 本文首先介绍并查集的定义、原理及...

    老白
  • LeetCode 477 Total Hamming Distance

    The Hamming distance between two integers is the number of positions at which th...

    Yano_nankai
  • DFS

    深度优先搜索算法(Depth-First-Search),是搜索算法的一种。是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所有边都己被探寻过,搜...

    AngelNH
  • Hive在load data时注意事项

    create table if not exists bdp_log(         tableName string ,             dat...

    幽鸿
  • LeetCode 200. Number of Islands(并查集)

    ShenduCC
  • 【每日一练】第001期--两数之和

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    会呼吸的Coder
  • 数据结构和算法——动态规划

    一、动态规划的思想     动态规划(dynamic programming)是一种算法设计的思想,主要是将一个问题划分成几个更小的问题,并对这样更小的问题进行...

    zhaozhiyong

扫码关注云+社区

领取腾讯云代金券