ZeroJudge F677: 並查集練習

有 N 個人，編號 0～N-1，0 號染上了嚴重的傳染性疾病，有與 0 直接或間接接觸的人都需要隔離。請問有多少人需要隔離?

範例測資

範例輸入範例輸出
第一行有兩個數字 N 和 M，接下來有 M 行，每一行有 2 個數字 A 和 B，代表 A 和 B 有接觸過。輸出有多少人需要隔離。
5 3
1 0
0 3
2 4		3
ZeroJudge F677 範例測資

解題思路

使用 Map 來紀錄每一個人的最底層接觸者，一開始將所有人的 Map 值都預設為 -1。

宣告一個函式 findEnd，需要一個參數 N，如果 N == -1 || Map[N] == -1，return N。如果 Map[N] == N，return N。否則 return findEnd(Map[N])。

輸入資料時，如果兩個人都沒有接觸史，則要判斷其中是否有 0，如果有的話就要將另一個人的 Map 值設定為 0。如果兩個人都有接觸史，則要判斷其中有沒有 0，如果有 0 的話就將另一個人的 Map[findEnd(另一個人)] 設為 0，否則就將其設為 findEnd(另一個人)。如果是一個有一個沒有，則將沒有的人的 Map 值設定成 findEnd(另一個人)。

最後跑一個從 0 到 N-1 的迴圈，如果 findEnd(Map[目前數字]) == 0，就將答案 +1。

範例程式碼－ZeroJudge F677: 並查集練習

#include <iostream>
#include <map>
using namespace std;

map<int, int>MAP;

void virus(const int a, const int b) {
    if (MAP[a] == -1 && MAP[b] == -1) {
        if (b == 0) {
            MAP[a] = b;
            MAP[b] = b;
        }
        else {
            MAP[a] = a;
            MAP[b] = a;
        }
    }
    else if (MAP[a] != -1 && MAP[b] != -1) {
        if (findEnd(MAP[b]) == 0) MAP[findEnd(a)] = 0;
        else MAP[findEnd(b)] = findEnd(a);
    }
    else {
        if (MAP[a] != -1) MAP[b] = findEnd(a);
        else MAP[a] = findEnd(b);
    }
}

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

//ZeroJudge F677
//Dr. SeanXD
標籤

相關文章

發佈留言