Penney's Blogs

言必行，行必果

0%

05-树8 File Transfer

发表于 分类于 Valine：
本文字数： 3.7k 阅读时长 ≈ 3 分钟

​ 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:

1
I c1 c2

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

1
C c1 c2

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

1
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:

1
2
3
4
5
6
7
8
5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
S

Sample Output 1:

1
2
3
4
no
no
yes
There are 2 components.

Sample Input 2:

1
2
3
4
5
6
7
8
9
10
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:

1
2
3
4
5
no
no
yes
yes
The network is connected.

步骤

  1. 输入测试样例次数n,初始化数组S
  2. 循环读取操作，根据不同字符进行不同操作

编码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10000

typedef int ElementType;  //默认元素可以用非负整数表示
typedef int SetName;; // 默认用根结点的下标作为集合的名称
typedef ElementType SetType[MAXSIZE];//各结点的父结点集合，根结点为负数，数值为树高

void Initialization(SetType S, int N);

SetName Find(SetType S, ElementType X);

void Union(SetType S, SetName Root1, SetName Root2);

void InputConnection(SetType S);

void CheckConnection(SetType S);

void CheckNetWork(SetType S, int N);

int main() {
   SetType S;
   int n;
   char in;
   // 1.输入测试样例次数n,初始化数组S
   scanf("%d\n", &n);
   Initialization(S, n);
   do {
       // 2.循环读取操作，根据不同字符进行不同操作
       scanf("%c", &in);
       switch (in) {
           case 'I':
               InputConnection(S);
               break;
           case 'C':
               CheckConnection(S);
               break;
           case 'S':
               CheckNetWork(S, n);
               break;
       }
   } while (in != 'S');

   return 0;
}

//输入结点并联合
void InputConnection(SetType S) {
    ElementType u, v;
    SetName Root1, Root2;
    // 1.读取两个结点值u,v
    scanf("%d %d\n", &u, &v);
    // 2.找到两个结点的根结点Root1,Root2
    Root1 = Find(S, u - 1);
    Root2 = Find(S, v - 1);
    // 3.如果两根点不同，则两结点相结合
    if (Root1 != Root2)
        Union(S, Root1, Root2);
}

//检查两点联通性
void CheckConnection(SetType S) {
    ElementType u, v;
    SetName Root1, Root2;
    // 1.读取两个结点值u,v
    scanf("%d %d\n", &u, &v);
    // 2.找到两个结点的根结点Root1,Root2
    Root1 = Find(S, u - 1);
    Root2 = Find(S, v - 1);
    // 3.如果两结点相同，打印yes，不同打印no
    if (Root1 == Root2) {
        printf("yes\n");
    } else {
        printf("no\n");
    }
}

//检查整个网络联通性
void CheckNetWork(SetType S, int N) {
    int i, counter = 0;
    // 1.遍历数组Set，检查所有结点的父结点，记录为负数的根结点数
    for (i = 0; i < N; i++) {
        if (S[i] < 0)
            counter++;
    }
    // 2.根据不同的根结点数counter打印输出
    if (counter == 1) {
        printf("The network is connected.\n");
    } else {
        printf("There are %d components.\n");
    }
}

// 初始化结点数组
void Initialization(SetType S, int N) {
    for (int i = 0; i < N; ++i) {
        S[i] = -1;
    }
}

// 查找x结点的根结点
SetName Find(SetType S, ElementType X) {
    // 1.遍历数组S,直到找根结点,S[x]为负数
    for (; S[X] >= 0; X = S[X]);
    return X;
}

// 联合两棵树Root1,Root2
void Union(SetType S, SetName Root1, SetName Root2) {
    // Root1,Root2为不同集合的根结点,
    // 将根结点的值表示树的深度，负数表示为根结点
    // 1.合并两树，树深度较小的并到深度较大的上，这样才不会增加树的高度
    if (S[Root2] < S[Root1])
        // Root2的深度更大，需要将Root1并到Root2上
        S[Root1] = Root2;
    else {
        // 2.如果两树深度相同，则将Root2并到Root1上，Root1深度加1
        if (S[Root1] == S[Root2])
            S[Root1]--;
        S[Root2] = Root1;
    }
}

小结：

  1. 各结点的父结点用数组SetType存储，初始化为-1，根结点无父结点为负值
  2. 数组SetType，如果是根结点存负数，数值为树的高度
  3. 判断根结点是否相同判断是否同一棵树
  4. 树的高度较低者并在较高者上Union，减小查找根结点Find遍历的次数