ZeroJudge A445: 新手訓練系列 – 我的朋友很少

我的朋友很少～但是朋友的朋友就是我的朋友！

範例測資

範例輸入範例輸出
第一行有三個正整數 N、M、Q (N <= 10000，M <= 10000，Q <= 100000)，代表有 N 個人、M 筆朋友關係、Q 筆詢問。
接下來有 M 行， 每行有兩個正整數 A 和 B (A、B <= N)，代表 A 和 B 有朋友關係。
再來有 Q 行， 每行兩個正整數 P 和 Q (P、Q <= N )。		請輸出 P 和 Q 是不是朋友，如果是請輸出 「:)」，否則請輸出 「:(」。
5 3 2
1 2
2 5
3 4
1 5
1 3		🙂
🙁

解題思路

宣告一個陣列代表每一個人的最底層朋友是誰，每一個人預設值為 0。如果收到人的時候這個人的陣列值為 0，代表還沒有紀錄，所以將陣列值設為自己。

宣告一個函式 findEnd 用來尋找最底層的朋友，有一個參數 N，如果 N 的陣列值為 0 或是自己就 return N，否則就 return findEnd(陣列值[N])。

收到資料的時候將 陣列值[findEnd(B)] 設為 findEnd(A)。最後只需要確認 陣列值[P] 是否等於 陣列值[Q]，如果相同就代表這兩人是朋友。

範例程式碼－ZeroJudge A445: 新手訓練系列 – 我的朋友很少

#include <iostream>
using namespace std;

int MAP[870000] = {};

int findEnd(const int N) {
    const int MM = MAP[N];
    if (MM == 0 || MM == N) return N;
    return findEnd(MM);
}

void line(const int a, const int b) {
    if (MAP[a] == 0) MAP[a] = a;
    if (MAP[b] == 0) MAP[b] = b;
    MAP[findEnd(b)] = findEnd(a);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cout.sync_with_stdio(0);
    cout.tie(0);
    int N, M, Q;
    cin >> N >> M >> Q;
    for (int i = 1; i<=N; i++) MAP[i] = 0;
    for (int i = 0; i<M; i++) {
        int a, b;
        cin >> a >> b;
        line(a, b);
    }
    for (int i = 0; i<Q; i++) {
        int a, b;
        cin >> a >> b;
        if (findEnd(a) == findEnd(b)) cout << ":)\n";
        else cout << ":(\n";
    }
}

//ZeroJudge A445
//Dr. SeanXD
標籤

相關文章

發佈留言