ZeroJudge 解題筆記：f260. 愛八卦的同學

作者：王一哲
日期：2025年10月4日


ZeroJudge 題目連結：f260. 愛八卦的同學

解題想法

我用 BFS 找連通區塊數量，不過用 Python 的速度太慢，用 C++ 解題也要 0.3 s。

Python 程式碼

速度太慢，只能通過一筆測資。

import sys
from collections import deque

for line in sys.stdin:
    n, k = map(int, line.split())  # n 個人，k 組關係
    adj = [[] for _ in range(n)]  # 每個人與其它人的關係
    for _ in range(k):  # 讀取 k 行資料
        u, v = map(int, sys.stdin.readline().split())  # u, v 是朋友
        adj[u].append(v)
        adj[v].append(u)
    cnt = 0  # 小團體數量
    visited = [False]*n  # 是否已經檢查過
    for i in range(n):  # 依序讀取每一個人
        if visited[i]: continue  # 如果 i 已經檢查過，找下一個人
        visited[i] = True  # 設定為 True
        cnt += 1
        que = deque([i])
        while que:
            v = que.popleft()
            for u in adj[v]:
                if visited[u]: continue
                que.append(u)
                visited[u] = True
    print(cnt)

C++ 程式碼

使用時間約為 0.3 s，記憶體約為 588 kB，通過測試。

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int n, k;  // n 個人，k 組關係
    while(scanf("%d %d", &n, &k) != EOF) {
        vector<vector<int>> adj (n);  // 每個人與其它人的關係
        for(int i=0; i<k; i++) {  // 讀取 k 行資料
            int u, v; scanf("%d %d", &u, &v);  // u, v 是朋友
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        int cnt = 0;  // 小團體數量
        bool visited[n] = {0};  // 是否已經檢查過
        for(int i=0; i<n; i++) {  // 依序讀取每一個人
            if (visited[i]) continue;  // 如果 i 已經檢查過，找下一個人
            visited[i] = true;  // i 已走訪
            cnt++;  // 小團體數量加 1
            queue<int> que; que.push(i);  // 待走訪佇列加入 i
            while(!que.empty()) {  // 如果 que 有資料繼續執行
                int v = que.front(); que.pop();  // 取出 que 最前面的節點
                for(auto u : adj[v]) {  // 依序讀取與 v 相連的節點
                    if (visited[u]) continue;  // 如果 u 已經檢查過，找下一個人
                    visited[u] = true;  // u 已走訪
                    que.push(u);  // u 加入 que
                }
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}