APCS 實作題 10603 第2題小群體參考解法

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

此題在高中生程式解題系統的題號為：c291: APCS 2017-0304-2小群體。

題目簡短說明如下：
好友的關係會形成一些小群體。例如 N=10，好友編號如下，
0 的好友是 4，4 的好友是 6，6 的好友是 8，8 的好友是 5，5 的好友是 0，所以 0、4、6、8、和 5 就形成了一個小群體。另外，1 的好友是 7 而且 7 的好友是 1，所以 1 和7 形成另一個小群體，同理，3 和 9 是一個小群體，而 2 的好友是自己，因此他自己是一個小群體。總而言之，在這個例子裡有 4 個小群體：{0,4,6,8,5}、{1,7}、{3,9}、{2}。

延伸：輸出各小群體內每個人的編號，例如上述例子為{0,4,6,8,5}、{1,7}、{2}、{3,9}。

解法一：用陣列
用兩個陣列，一個(f [50000])用來記錄自己的好友是誰，一個(g[50000])用來記錄有沒有加入到群體裡。

尚未組成群體：

群體編號為 1：

群體編號為 2：

群體編號為 3：

群體編號為 4：


C 程式碼：
 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
#include <stdio.h>

int main(void) {
    int n;

    while(scanf("%d", &n) == 1)
    {
        int f[50000];   // 自己的好友是誰
        char g[50000] = {0};  // 有無加入群體

        for(int i = 0; i < n; i++)
            scanf("%d", &f[i]);

        int grpCnt = 0;     // 紀錄有幾個群體
        int nxt = 0;        // 自己的好友是誰
        for(int i = 0; i < n; i++)
        {
            if(g[i] == 0) // 尚未加入群體
            {
                nxt = i;              // 目前尚未加入群體的人
                do
                {
                    g[nxt] = grpCnt + 1;    // 已加入此群體
                    nxt = f[nxt];       // 換下一位好友
                }while(g[nxt] == 0);
                grpCnt++;               // 已找完群體的人數，所以將群體數加一
            }
        }

        printf("%d\n", grpCnt);

    }
    return 0;
}

C++ 程式碼：
 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
#include <iostream>

using namespace std;

int main(void) {
    int n;

    while(cin >> n)
    {
        int f[50000];   // 自己的好友是誰
        char g[50000] = {0};  // 有無加入群體

        for(int i = 0; i < n; i++)
            cin >> f[i];

        int grpCnt = 0;     // 紀錄有幾個群體
        int nxt = 0;        // 自己的好友是誰
        for(int i = 0; i < n; i++)
        {
            if(g[i] == 0) // 尚未加入群體
            {
                nxt = i;              // 目前尚未加入群體的人
                do
                {
                    g[nxt] = grpCnt + 1;   // 已加入此群體
                    nxt = f[nxt];       // 換下一位好友
                }while(g[nxt] == 0);
                grpCnt++;               // 已找完群體的人數，所以將群體數加一
            }
        }

        cout << grpCnt << endl;

    }
    return 0;
}

Python 程式碼：
 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
while True:
    try:
        n = int(input())
        f = input()
        # 紀錄自己的好友是誰
        f = list(map(int, f.split()))

        # 有無加入群體
        g = []

        # 群體編號為 0 代表尚未分群到
        for i in range(n):
            g.append(0)

        # 紀錄有幾個群體
        grpCnt = 0

        # 從 0 號開始找起
        for i in range(n):
            if g[i] == 0:
                nxt = i  # 目前尚未加入群體的人

                while True:
                    g[nxt] = grpCnt + 1  # 已加入此群體
                    nxt = f[nxt]         # 換自己好友的編號
                    if g[nxt] != 0:      # 自己好友已有加入群體
                        break
                grpCnt = grpCnt + 1      # 已找完群體的人數，所以將群體數加一

        print(grpCnt)
                
    except EOFError:
        break

註：解法一的程式碼是可以輸出各小群體內每個人的編號，如{0,4,6,8,5}、{1,7}、{2}、{3,9}的結果，只是程式碼沒有做輸出。

解法二：用 (key, value) 的資料結構
C語言本身沒有提供 (key, value) 這種資料結構，要自己做一個，有興趣的讀者可以試試。而C++可以使用 map 這個 container；Python 則是用 Dictionary。程式的資料結構就會變成如下：

每次都從尚未分到群體的最小編號者開始找起，整個流程如下。

首先從編號 0 開始找起

會找出群體為{0,4,6,8,5} 。

從編號  1 找起
會找出群體為{1,7} 。

從編號 2 找起
會找出群體為{2} 。

從編號 3 找起
會找出群體為{3,9} 。


C++ 程式碼：
 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
#include <iostream>
#include <map>

using namespace std;

int main(void) {
    int n;

    while(cin >> n)
    {
        map<int, int> m;
        for(int i = 0; i < n; i++)
        {
            int v;
            cin >> v;
            m[i] = v;
        }

        int grpCnt = 0;     // 紀錄有幾個群體

        while(!m.empty())
        {
            // 每群都從未分到群體的最小編號開始
            int f = m.begin()->first;       // 自己的編號
            int nxtF = m.begin()->second;   // 自己好友的編號

            //cout << "{";
            while(true)
            {
                //cout << f << ",";
                m.erase(f);                     // 已加入群體，所以從表中刪除
                f = nxtF;                       // 換成自己好友編號
                if(m.find(nxtF) == m.end())     // 找自己好友的好友編號
                    break;                      // 若找不到，代表此群體已建立好
                nxtF = m.find(nxtF)->second;    // 換成自己好友的好友編號
            }
            //cout << "}" << endl;
            grpCnt++;
        }

        cout << grpCnt << endl;

    }
    return 0;
}

Python 程式碼：
 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
while True:
    try:
        n = int(input())
        f = input()
        # 紀錄自己的好友是誰
        f = list(map(int, f.split()))

        m = {}
        for i in range(n):
            m[i] = f[i]
       
        # 紀錄有幾個群體
        grpCnt = 0

        while len(m) > 0:
            # 每群都從未分到群體的最小編號開始
            f = list(m.keys())[0]         # 自己的編號
            nxtF = list(m.values())[0]    # 自己好友的編號

            # print('{', end='')
            while True:
                del m[f]    # 已加入群體，所以從表中刪除
                #print(f,',', end='')
                f = nxtF    # 換成自己好友編號
                if not f in m.keys():   # 找自己好友的好友編號
                    break               # 若找不到，代表此群體已建立好
                nxtF = m[nxtF]          # 換成自己好友的好友編號

            # print('}')
            grpCnt = grpCnt + 1      # 已找完群體的人數，所以將群體數加一

        print(grpCnt)
                
    except EOFError:
        break

註：解法二的程式碼是可以輸出各小群體內每個人的編號，如{0,4,6,8,5}、{1,7}、{2}、{3,9}的結果，而該部分的程式碼被註解掉。

Labels: , , ,