04-树5. File Transfer (25)

Posted on   |   In   |  

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.

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
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.

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
#include<iostream>
#include<string>
#include<map>
using namespace std;

int N = 0;  //the total number of computers in a network

int FindPosition(map<int, int> &nodeMap, int data)
{
//    int i = data;
//    for(; nodeMap[i] >= 0; i = nodeMap[i]);
//    return i;
    if(nodeMap[data] > 0)
    {
        nodeMap[data] = FindPosition(nodeMap,nodeMap[data]);//nodeMap[data];
        return nodeMap[data];
    }
    return data;
}
bool Find(map<int, int> &nodeMap, int parentNode, int childNode)
{
    int pNRP = FindPosition(nodeMap, parentNode); //pNRP = parentNodeRootPosition
    int cNRP = FindPosition(nodeMap, childNode);    //cNRP = childNodeRootPosition
    if(pNRP != cNRP )
    {
        return false;
    }
    return true;
}
void Union(map<int, int> &nodeMap, int parentNode, int childNode)
{
    int pNRP = FindPosition(nodeMap, parentNode);
    int cNRP = FindPosition(nodeMap, childNode);
    if(pNRP != cNRP)    //如果不在同一个集合里，则合并
    {
        nodeMap[parentNode] = cNRP;
        --N;
        //根结点的父结点是负数，绝对值代表该集合个数
/*        if(nodeMap[pNRP] >= nodeMap[cNRP])  //pNRP所在的集合元素较少，将pNRP所在集合元素加入cNRP所在集合
        {
            nodeMap[cNRP] -= 1;
            nodeMap[parentNode] = cNRP;
        }
        else
        {
            nodeMap[pNRP] -= 1;
            nodeMap[childNode] = pNRP;
        }
        */
    }
}
int main()
{

    cin >> N;
    map<int, int> nodeMap; //<data,<position,parent>>
    for(int i = 1; i <= N; ++i)
    {
        nodeMap[i] = -1;
    }
    char state;
    while(cin >> state)
    {
        if(state == 'S')
        {
            break;
        }
        int parentNode = 0, childNode = 0;
        cin >> parentNode >> childNode;
        if(state == 'C')
        {
            if(Find(nodeMap, parentNode, childNode))
            {
                cout << "yes" << endl;
            }
            else
            {
                cout << "no" << endl;
            }
        }
        else if(state == 'I')
        {
            Union(nodeMap, parentNode, childNode);
        }
    }
//    cout << (countNum == 1? "The network is connected." : "There are " + itoa(countNum) + " components.") << endl;
    if(N == 1)
    {
        cout << "The network is connected." << endl;
    }
    else
    {
        cout << "There are " << N << " components." << endl;
    }
    return 0;
}

看完mooc，按照视频里老师所说的方法是过测试样例没问题，但是后面有测试点就会运行超时，本想着建立一个10002大小的数组是用内存换时间，觉得不好，就没有用，使用map来做，但是还是过不了，然后就参考别人AC的代码,最后发现人家直接搞个10002的数组比我这map还快不说，内存占用还小。本题主要是FindPosition算法，如果用老师说的，运行超时，最后我仿照别人的思路，每次find的时候自动调整树，将一棵树的所有子结点都指向根结点，这样就AC了。
测试结果：
|测试点| 结果| 用时(ms)| 内存(kB)| 得分/满分|
|:—:|
|0 |答案正确| 1| 180 |7/7
|1 |答案正确| 1| 180 |7/7
|2 |答案正确| 1| 308 |1/1
|3 |答案正确| 2| 692 |1/1
|4 |答案正确| 35| 692 |4/4
|5 |答案正确| 39| 768 |4/4
|6 |答案正确| 36| 820 |1/1

这里贴一个别人的代码,他用的和我上面参考的那篇博客方法差不多，利用父结点等于自身下标就是根节点，每次find都会更新树，将树的所有子孙结点全部指向根结点。结合上面那篇博客所用的计数方法，每合并一次，根结点就少一个，所以采用--N，这样就不用最后遍历整个数组了。
不过这个代码用的是动态数组，按道理来说动态数组因为没有固定大小，不会浪费内存，占用内存小，但是实际测试发现，动态数组消耗的内存要比静态数组大，所以以后写代码如果题目的数据有上限，就直接声明最大上限大小的静态数组。

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
#include <iostream>
#define ElementType int
using namespace std;
int num = 0;
int *S;
int Find( ElementType X )
{
    if(S[X]==X)
        return X;
    return S[X]=Find(S[X]);
}

void Union( ElementType X1, ElementType X2)
{
    int Root1, Root2;
    Root1 = Find(X1);
    Root2 = Find(X2);
    if ( Root1 != Root2 )
    {
        if(S[Root1] < S[Root2])
        {
            S[Root2] = Root1;
        }
        else
        {
            S[Root1] = Root2;
       }
      --num;
    }
}

int main()
{
    cin >> num;
    char choose;
    int c1, c2;
    S = new int[num+1];
    for(int i=0; i<=num; i++)   // 初始化
        S[i] = i;
    while(1)
    {
        cin >> choose;
        if(choose == 'S')
            break;
        cin >> c1 >> c2;
        if(choose == 'I')
            Union(c1, c2);
        if(choose == 'C')
        {
            if(Find(c1) == Find(c2))
                cout << "yes" << endl;
            else
                cout << "no" << endl;
        }
    }
    if(num == 1)
         cout << "The network is connected." << endl;
    else
        cout << "There are " << num << " components." << endl;
    return 0;
}