【題解】ZeroJudge c291: APCS 2017-0304-2小群體

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=c291
【解題想法】

  • 題目保證每個人的好友編號絕對不會重複。
  • fr[ ]:紀錄每個人的好友編號。
  • group[ ]:紀錄每個人所屬的群體。初始值為 -1
  • 每次發現一個還未檢查過的人,把他所屬的群體設為自己,然後開始把他的朋友,朋友的朋友….都加到同一個群體,直到形成一個環
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 50005;
int fr[maxn]; //friend
int group[maxn]; //group

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;
    for (int i=0; i<N; i++){
        cin >> fr[i]; //紀錄每個人的好友編號
    }
    memset(group, -1, sizeof(group));
    for (int i=0; i<N; i++){
        if (group[i] >= 0) continue;
        group[i] = i;
        int now = i;
        while (fr[now] != i){
            group[fr[now]] = i;
            now = fr[now];
        }
    }
    int ans = 0;
    for (int i=0; i<N; i++){
        ans += (group[i] == i);
    }
    cout << ans << '\n';

    return 0;
}

Python code

# 本題輸入包含若干筆測試資料
while True:
    try:
        N = int(input()) # 團體中人數
        friend = list(map(int, input().split())) # 讀入每個人的好友編號
        ans = 0
        for i in range(N):
            if friend[i] != -1: # 發現一個還未被檢查過的人
                cur = i # cur (current): 目前受檢查者的編號
                while True:
                    nxt = friend[cur] # nxt (next): 他的好友的編號
                    friend[cur] = -1 # 標註成檢查過了
                    if nxt == i: # 形成一個環
                        break
                    cur = nxt # 繼續檢查朋友的朋友
                ans += 1
        print(ans)
    except:
        break
分享本文 Share with friends