高中生程式解題系統 c291: APCS 2017-0304-2小群體－資工趴趴熊的小天地

Content

問題描述

Q同學正在習程式， P老師出了以下的題目讓他練習。

一群人在一起時經常會形成一個一個的小群體。假設有 N個人，編號由 0到 N-1，每個人都寫下他最好朋友的編號（最好朋友有可能是他自己的編號，如果他自己沒有其他好友），在本題中，每個人的好友編號絕對不會重複，也就是說0到 N-1每個數字都恰好出現一次。

這種好友的關係會形成一些小群體。例如 N=10，好友編號如下，

自己編號	0	1	2	3	4	5	6	7	8	9
好友編號	4	7	2	9	6	0	8	1	5	3

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} 。本題的問題是：輸入每個人好友編號，計算出總共有幾小群體。

Q同學想了卻不知如何下手，和藹可親的P老師於是給了他以下的提示：如果你從任何一人x開始，追蹤他的好友，好友的好友，….，這樣一直下去，定會形成個圈回到 x，這就是一個小群體。如果我們追蹤的過程中把追蹤過的加以標記，很容易知道哪些人已經追蹤過，因此當一個小群體找到之後，我們再從任何還未蹤過的開始繼續找下一個小群體，直到所有人都追蹤完畢。

Q同學聽完之後很順利的成了作業。

在本題中，你的任務與Q同學一樣：給定群人的好友，請計算出小群體個數。

原題pdf檔

Input

第一行是一個正整數N，說明團體中人數。

第二行依序是 0的好友編號、1的好友編號、…… 、N-1的好友編號。共有N個數字，包含 0到 N-1的每個數字恰好出現一次，數字間會有一個空白隔開。

Output

請輸出小群體的個數。不要有任何多餘的字或空白，並以換行字元結尾。

Sample Input #1

10
4 7 2 9 6 0 8 1 5 3

Sample Output #1

Sample Input #2

3
0 2 1

Sample Output #2

方法一: (Union-Find Algorithm 並查集)

https://www.youtube.com/watch?v=blnu0BK2U_o

python:

"""
Union-Find Algorithm 並查集disjoint set
處理若干個集合，此外彼此之間沒有交集

可以做到3件事:
1.判斷某個節點的所在子圖(找到最上面的祖先節點)
2.判斷某兩個節點是否在同一子圖(判斷祖先節點是否一樣)
3.合併某兩個節點所在子圖(將兩個的祖先節點合併)

"""
def find(x):#用於找到最上面的節點
    if arr[x]==x:return x
    else:
        arr[x]=find(arr[x])
        return arr[x]

def unint(x,y):#作用於將兩個祖先節點合併
    global arr
    x,y=find(x),find(y)
    if x==y:return
    if x<=y:arr[x]=y #若今天x比較小，就把x的父節點存成y
    else:arr[y]=x #把y的父節點存成x

while True:
    try:
        n=int(input())
        arr=[i for i in range(n)]
        f=[int(x) for x in input().split()] 
        ans=0

        for i in range(n):
            unint(f[i],i)
        for i in range(n):
            find(i)
        for i in range(n):
            if arr[i]==i:
                ans+=1
        print(ans)

    except:break

方法二:

https://yunlinsong.blogspot.com/2020/01/apcs-10603-2.html

while True:
    try:
        n = int(input())
        # 紀錄自己的好友是誰
        f = list(map(int,  input().split()))
        g = [0]*n# 有無加入群體
        ans = 0# 紀錄有幾個群體

        # 從 0 號開始找起，若為0，將朋友編號記起來
        for i in range(n):
            if g[i] == 0:
                nxt = i  # 目前尚未加入群體的人
                while True:
                    g[nxt] = ans + 1  # 已加入此群體
                    nxt = f[nxt]         # 換自己好友的編號
                    """上面兩行一職重複循環(這就是查找過程)，直到下面這個if條件成立"""
                    if g[nxt] != 0: break      # 自己好友已有加入群體
                ans +=1     # 已找完群體的人數，所以將群體數加一(這就是最後要輸出的答案)

        print(ans)
                
    except EOFError:
        break

方法三:

利用字典的方式

while True:
    try:
        n = int(input())
        f = input()
        # 紀錄自己的好友是誰
        f = list(map(int, f.split()))
        """這裡在建造字典"""
        m = {}
        for i in range(n):
            m[i] = f[i]      
        ans = 0# 紀錄有幾個群體
        while len(m) > 0:
            # 每群都從未分到群體的最小編號開始
            key = list(m.keys())[0]         # 自己的編號
            value = list(m.values())[0]    # 自己好友的編號

            # print('{', end='')
            while True:
                del m[key]    # 已加入群體，所以從表中刪除
                #print(f,',', end='')
                key = value    # 將value換成key(之後繼續查找)
                if not key in m.keys():   # 找自己好友的好友編號
                    break               # 若找不到，代表此群體已建立好
                value = m[value]          # 換成新的value
                """
                value = m[value]這行一定要寫在if條件後面
                因為今天完成一個小群體，我們前面會把咬找到的刪掉，那今天完成一個小群體就是回茶道重複的，可是已經被我們刪掉了
                所以會查找不到，會出錯
                """
            # print('}')
            ans+=1     # 已找完群體的人數，所以將群體數加一
        print(ans)
    except EOFError:
        break