ZeroJudge 解題筆記：a445. 新手訓練系列- 我的朋友很少

作者：王一哲
日期：2025年1月26日



ZeroJudge 題目連結：a445. 新手訓練系列- 我的朋友很少

解題想法

先用鄰接串列儲存節點之間的連接方式，注意，這題是無向圖，而且測資中某些行可能 兩個一樣的數字，因為不能自己連到自己，要記得排除。
由於題目要問 A 和 B 是否為朋友，只要 A、B 能夠相連就是朋友，理論上可以用 BFS 從 A 開始測試，如果能夠走到 B，兩人就是朋友。但這題要測試很多次，比較有效率的作法是利用併查集及路徑壓縮，先將每個點的父節點都設定成自己，再用 BFS 或是遞迴，從某一個點 n 開始，將所有與 n 相連的點其父節點都設定成 n，檢測時只要看這兩個點的父節點是否相同，就可以知道兩個點是否相連。

Python 程式碼

使用時間約為 0.7 s，記憶體約為 5.8 MB，通過測試。

from collections import deque

def rfind(n, r):  # 自訂函式，輸入節點 n，根節點 r，路徑壓縮
    que = deque([n])  # 待走訪佇列，先放入 n
    while que:  # 如果 que 還有資料繼續執行
        u = que.popleft()  # 從 que 最前面讀取並移除資料
        for v in adj[u]:  # 依序讀取與 u 相連的節點 v
            if parent[v] == v:  # 如果 v 還沒有找到父節點
                parent[v] = r  # 將 v 的父節點設定成 r
                que.append(v)  # 將 v 加入 que
# 讀取資料
N, M, Q = map(int, input().split())  # N 個人，M 筆朋友關係，Q 筆詢問
adj = [[] for _ in range(N+1)]  # 人之間的關係，無向圖，人的編號為 1 ~ N
for _ in range(M):  # 讀取 M 行資料
    A, B = map(int, input().split())  # A 和 B 有朋友關係
    if A == B: continue  # 如果 A、B 是同一個人，找下一筆資料
    adj[A].append(B)
    adj[B].append(A)
# 找每個節點的父節點
parent = list(i for i in range(N+1))  # 每個節點的父節點，先設定成自己的編號
for i in range(1, N+1):  # 依序掃過 1 ~ N 號
    if parent[i] == i and adj[i]:  # 如果 i 還沒有找到父節點而且 i 有相連的點
        rfind(i, i)  # 呼叫 rfind，將與 i 相連的點其父節點都設定成 i
# Q 行待測資料
for _ in range(Q):
    A, B = map(int, input().split())  # 要測試的 A 和 B
    print(":)" if parent[A] == parent[B] else ":(")

C++ 程式碼

使用時間約為 41 ms，記憶體約為 3.3 MB，通過測試。

#include <iostream>
#include <vector>
#include <queue>
#define maxn 100000
using namespace std;

vector<int> parent (maxn);  // 每個節點的父節點
vector<vector<int>> adj (maxn);  // 人之間的關係，無向圖，人的編號為 1 ~ N

void rfind(int n, int r) {  // 自訂函式，輸入節點 n，根節點 r，路徑壓縮
    queue<int> que; que.push(n);  // 待走訪佇列，先放入 n
    while(!que.empty()) {  // 如果 que 還有資料繼續執行
        int u = que.front(); que.pop();  // 從 que 最前面讀取並移除資料
        for(int v : adj[u]) {  // 依序讀取與 u 相連的節點 v
            if (parent[v] == v) {  // 如果 v 還沒有找到父節點
                parent[v] = r;  // 將 v 的父節點設定成 r
                que.push(v);  // 將 v 加入 que
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    /* 讀取資料 */
    int N, M, Q; cin >> N >> M >> Q;  // N 個人，M 筆朋友關係，Q 筆詢問
    adj.resize(N+1);  // 調整 adj 的大小
    for(int i=0; i<M; i++) {  // 讀取 M 行資料
        int A, B; cin >> A >> B;  // A 和 B 有朋友關係
        if (A == B) continue;  // 如果 A、B 是同一個人，找下一筆資料
        adj[A].push_back(B);
        adj[B].push_back(A);
    }
    /* 找每個節點的父節點 */
    parent.resize(N+1);  // 調整 parent 的大小
    for(int i=1; i<=N; i++) parent[i] = i;  // 每個節點的父節點，先設定成自己的編號
    for(int i=1; i<=N; i++) {  // 依序掃過 1 ~ N 號
        // 如果 i 還沒有找到父節點而且 i 有相連的點，呼叫 rfind，將與 i 相連的點其父節點都設定成 i
        if (parent[i] == i && !adj[i].empty()) rfind(i, i);
    }
    /* Q 行待測資料 */
    for(int i=0; i<Q; i++) {
        int A, B; cin >> A >> B;  // 要測試的 A 和 B
        cout << (parent[A] == parent[B] ? ":)\n" : ":(\n");
    }
    return 0;
}