1. 小群體
    1. 題目
    2. 解法

小群體

最後更新: 作者: 字数: 237 预计阅读时间: 1min

小群體

APCS歷屆

題目

PDF
大家可以看一下第二題，原則上就是朋友之間會連到另一個朋友，如果可以連成一圈，最後回到一開始那個人，那就是群體，而我們要的就是計算有幾個群體。

解法

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
# 登記每個人是否都走過
def walk(): #main code
    list3 = [False for i in range(len(list1))]
    #print(list3)
    #now = 0
    count = 0
    for i in range(len(list1)):
        if list3[i] == False:
            list3[i] = True
            count += 1
            now = i
            #first = list3[now]
            while True:
                #k = 2
                if list3[list2[now]] == False:
                    list3[list2[now]] = True
                    now = list2[now]
                elif list3[list2[now]] == True:
                    break
    #print(count)
    return count

list1 = [i for i in range(3)]
list2 = [0, 2, 1]
list1 = [i for i in range(int(input()))]
list2 = list(map(int, input().split()))
print(walk(), end = "\n")

我的想法就是紀錄是否每個人都走過，用True or False來判斷，如果沒被走過我們就把count += 1並且開始走他的朋友直到走完那一個群體再繼續。