2.6 File Transfer（树，c）

File Transfer

• • • 集合的简化表示
    • 题意理解
    • 程序框架搭建
    • TSSN的实现
    • • 按秩归并（对union的改进）
      • 按高度归并
      • 按规模归并
      • 路径压缩（对find的改进）
    • 时间复杂度
    • 源码
    • • 运行

原题直达：05-树8 File Transfer

集合的简化表示

题意理解

• Sample Input 1:

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

• Sample Output 1:

nonoyesThere are 2 components.

• Sample Input 2:

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

• Sample Output 2:

nonoyesyesThe network is connected.

5代表计算机个数
C代表check表示查询3和2之间有没有联通，开始一条网线都没有，是不连通的，输出no
I 表示input输入，在3和2之间加一条网线…
S代表终止符
1自己是联通集（和自己联通），2，3，4，5是直接或间接联通的，所以输出系统里面有两个联通机

最后输出这个网络是联通的

程序框架搭建

假设集合里的每个元素都是独立的，每一个都是自己的根节点，所以只要把S里面的每个元素都定义成-1就可以了

• Input_connection 输入函数：读进两个计算机的编号，计算机是从1到n编号的，而集合S的下标是从0到n-1的，要做一个简单的映射，调用Find函数的时候，传进去的是u这台计算机的下标u-1，v也类似，即读进来两台计算机，分别查一下它们两个所属集合的根结点是什么，如果他们俩个还分属于不同集合的话，就在之间连一条网线，也就是把这两个集合合并在一起
• Check_connection 查询函数：如果在check里面两个函数是一样的，就说明两个集合本身是联通的，输出yes，否则没联通就输出no
• Check_network 检查网络是否联通，参数n表示有多少个根结点，即返回多少个联通集。扫描每一个s数组里的元素，只要他是小于0的不一，那么他是一个根节点，counter++;，最后数一下一共有多少个根节点，数完之后有两种情况，一种是只有一个根节点，表示整个集合全部联通了，否则就输出有多少个联通集

TSSN的实现

too simple sometimes naive(最原始简单版：很傻很天真)

按秩归并（对union的改进）

按高度归并

因为是负数，
，root2的高度要大于root1的高度，树高+1的话，意味着负值-1

按规模归并

任何时候归并了两棵树以后，最后结果树的规模都会改变，变成原来两棵树的规模之和，所以当集合2比较大的时候，把集合2的根节点做一个改变，加上原来集合1的规模，反之集合1规模改变，加上集合2的规模，
按秩归并最坏情况的树高：O(logN)

路径压缩（对find的改进）

把路径上的每一个根节点都贴到了根节点的下面，该Find函数的递归调用实际上是一个伪递归，非常容易被转换成循环，不用担心系统堆栈爆掉。

• 尾递归基于函数的尾调用, 每一级调用直接返回函数的返回值更新调用栈,而不用创建新的调用栈, 类似迭代的实现, 时间和空间上均优化了一般递归!

时间复杂度

当N充分大的时候，路径压缩比不做效率快的多，但是N只有10的4次方的时候，logN是一个很小的数字，很难比较两种方法优劣。

源码

#include#include#define MaxSize 10001typedef int ElementType;typedef int SetName;typedef ElementType SetType[MaxSize];void Init(SetType s, int n) {/*默认集合元素全部初始化为-1*//*for (; s[n]>=0; n=s[n])return n;*/for (int i = 0; i < n; i++)s[i] = -1;}/*路径压缩*/SetName Find(SetType s, int x) {if (s[x] < 0)  // 本身已经是根 return x;else  // 先找到根,把根变成 x 的父结点,再返回根 return s[x] = Find(s, s[x]);}/*按秩（规模）归并*/void Union(SetType s, SetName Root1, SetName Root2) {//S[root] = -元素个数if (s[Root1] < s[Root2]) {  //x1的元素多，少的并入多的中s[Root1] += s[Root2];s[Root2] = Root1;}else {s[Root2] += s[Root1];s[Root1] = Root2;}}/*输入函数*/void Input_connection(SetType s) {ElementType u, v;scanf("%d %d", &u, &v);SetName root1 = Find(s, u - 1);  // 以数组下标存值，下标与存值差 1 SetName root2 = Find(s, v - 1);if (root1 != root2)Union(s, root1, root2);}/*查询函数*/void check_connection(SetType s) {ElementType u, v;scanf("%d %d", &u, &v);SetName root1 = Find(s, u - 1);SetName root2 = Find(s, v - 1);if (root1 == root2)printf("yes\n");elseprintf("no\n");}/*检查网络是否联通，参数n表示有多少个根结点，即返回多少个联通集*/void check_network(SetType s, int n) {int counter = 0;for (int i = 0; i < n; i++) {if (s[i] < 0)counter++;}if (counter == 1)printf("The network is connected.");elseprintf("There are %d components.", counter);}int main() {SetType s;int n;char in;scanf("%d\n", &n);Init(s, n);do {//getchar();scanf("%c", &in);switch (in) {case 'I':Input_connection(s); break;case 'C':check_connection(s); break;case 'S':check_network(s, n); break;}} while (in != 'S');return 0;}

运行

5C 3 2noI 3 2C 1 5noI 4 5I 2 4C 3 5yesSThere are 2 components.