2017.3月大學程式設計先修檢測 實作題 第二題(小群體)

問題描述
Q同學正在習程式， P老師出了以下的題目讓他練習。
一群人在起時經常會形成個的小 群體。假設有 體。假設有 體。假設有 N個人，編號由 個人，編號由 個人，編號由 0到 N-1，每 個人都寫下他最好朋友的編號（有可能是自己，如果沒其 個人都寫下他最好朋友的編號（有可能是自己，如果沒其 個人都寫下他最好朋友的編號（有可能是自己，如果沒其 個人都寫下他最好朋友的編號（有可能是自己，如果沒其 他好友）， 他好友）， 在本題中， 每個人的 好友編號絕對不會重複，也就是說 好友編號絕對不會重複，也就是說 0到 N-1每個數字 都恰好 出現一次 出現一次 。
如：
好友編號
序號          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} 。

範例一：輸入 範例一：輸入
10
4 7 2 9 6 0 8 1 5 3
範例一：正確輸出 範例一：正確輸出
4
(說明）
4個小 群體是 {0,4,6,8,5 }, {1,7 }, {3,9 }和 {2}。
範例二：輸入 範例二：輸入
3
0 2 1
範例二：正確輸出 範例二：正確輸出
2
（說明）
2個小 群體分別是 {0},{1,2 }。

Code：
n=int(input()) #輸入好友個數
data=input() 
list=data.split(' ') # 將好友編號分開
w=[] #記錄好友編號
v=[] #記錄是否追蹤過
flag=0 #小群體個數
w=[int(x) for x in list] #將輸入的字串變整數
for i in range(n):
    v.append(0) #一開始都沒追蹤，設為0

for j in range(n):
    if v[j]==0: #從沒追蹤的開始追蹤，追蹤過的變為1
        if w[j]==j:#自己是自己的好友，算一個小群體
            flag+=1  #小群體直接加1
            v[j]=1#追蹤過的變為1
        else: #有其它人為好友
            nextone=j #用nextone來當暫存數
            while v[nextone]==0:#當沒拜訪過就繼續拜訪
                v[nextone]=1 #拜訪過的變為1
                nextone=w[nextone] #一直循環到成一小群體
            flag+=1 #成一小群體加1
    
print(flag) #印出小群體個數

😁 程式要寫註解，不然事後來看，就得多花時間才看得懂了!!!