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 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

P3808 【模版】AC自动机(简单版)

题目背景 这是一道简单的AC自动机模版题。 用于检测正确性以及算法常数。 为了防止卡OJ,在保证正确的基础上只有两组数据,请不要恶意提交。 题目描述 给定n个模...

34950
来自专栏武培轩的专栏

剑指Offer-链表中倒数第k个结点

题目描述 输入一个链表,输出该链表中倒数第k个结点。 思路 为了能够只遍历一次就能找到倒数第k个节点,可以定义两个指针: 快指针从链表的头指针开始遍历向前走k-...

36490
来自专栏书山有路勤为径

区间查找

给定一个排序数组nums(nums中有重复元素)与目标值target,如果 target在nums里出现,则返回target所在区间的左右端点下标,[左端点, ...

10020
来自专栏算法channel

深度优先搜索和回溯结合后的终极模板

昨天 这5道算法题 都可以套用这个模板 推送了一个深度搜索和回溯结合的题目和另4道类似题,今天,逐个分析后4道题,最后提炼出模板。

15700
来自专栏小樱的经验随笔

从零开始学建树(树的分治,树的重心)

分治算法在树的路径问题中的应用 一、树的分治算法 树的分治算法是分治思想在树型结构上的体现。 任一个具有n个节点的连通路,它的任何一棵树的树枝数为n-1 分治:...

29340
来自专栏wym

树状数组理论基础

  树状数组(binary indexed trees,二进制索引树),最早由Peter M. Fenwick于1994年以“A New Data Struct...

10220
来自专栏Bingo的深度学习杂货店

从M走到N最少步数

假设一个人站在 X 轴的正半轴上,起始点在 M 点(0 <= M <= 100000),他每次可以向左走一步,向右走一步,或者走到所在坐标乘以2的位置,最终来到...

15720
来自专栏大闲人柴毛毛

动态规划法(二)——弗洛伊德算法

问题描述 给定一个带权有向图,计算任意两结点间的最短路径。 迪杰斯特拉算法可以计算指定起点到所有结点的最短路径长度,因此分别对每个结点使用一次迪杰斯特拉...

40970
来自专栏拭心的安卓进阶之路

Java 集合深入理解(16):HashMap 主要特点和关键方法源码解读

前面我们介绍了 哈希相关概念:哈希 哈希函数 冲突解决 哈希表,这篇文章我们来根据 JDK 1.8 源码,深入了解下使用频率很高的 HashMap 。 读完本...

30450
来自专栏来自地球男人的部落格

[LeetCode] 119. Pascal's Triangle II

【原题】 Given an index k, return the kth row of the Pascal’s triangle. For exampl...

21360

扫码关注云+社区

领取腾讯云代金券