Buy Me a Coffee

APCS 題目小群體

題目描述

在這個APCS的練習題中，我們需要找出給定數字串中的小群體數量。一群人會根據他們的好友關係形成小群體，其中每個人只有一個最好的朋友，這種關係可能形成閉合的群體。

練習環境

如果沒有本地編譯環境，可以在以下網站進行練習：Programiz C++ Compiler

輸入輸出格式

  • 輸入：第一行包含一個正整數N，表示人數。第二行包含N個用空格隔開的數字，表示每個人的最好朋友的編號。
  • 輸出：輸出一個整數，表示小群體的總數。

解題思路

本題的核心是找出閉合的好友圈，即從一個人開始追蹤他的好友，直到回到起點。每找到一個這樣的圈，就算作一個小群體。

解題程式碼

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> friends;   // 儲存每個人最好朋友的編號
vector<bool> visited;  // 標記是否已訪問

// 深度優先搜尋找出小群體
void dfs(int idx) {
    visited[idx] = true;
    int next = friends[idx];
    if (!visited[next]) {
        dfs(next);
    }
}

int main() {
    int N;
    cin >> N;

    friends.resize(N);
    visited.assign(N, false);

    for (int i = 0; i < N; i++) {
        cin >> friends[i];
    }

    int groupCount = 0;
    for (int i = 0; i < N; i++) {
        if (!visited[i]) {
            dfs(i);
            groupCount++;
        }
    }

    cout << groupCount << endl;
    return 0;
}

評分說明

根據測試資料的不同，本題分為三個子題組，每個子題組的得分依據正確通過測試數據的數量而定。

  • 子題組1：20分，1 ≤ N ≤ 100，每個小群體最多2人。
  • 子題組2：30分，1 ≤ N ≤ 1,000，無其他限制。
  • 子題組3：50分，1,001 ≤ N ≤ 50,000，無其他限制。

通過這個練習，學生可以加深對於圖的遍歷和深度優先搜索（DFS）的理解，這對於解決APCS或其他程式設計考試中的問題非常有幫助。