ZeroJudge F677: Disjoint-Set Practice

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

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The first line contains two numbers, N and M. The next M lines each contain two numbers, A and B, indicating that A and B have had contact.Output how many people need to be quarantined.
5 3
1 0
0 3
2 4		3
ZeroJudge F677 Sample Test Case

Thought Process

Use a map to record the ultimate contact person for each individual, initially setting the map value for all people to -1.

Declare a function findEnd that takes a parameter N. If N == -1 or Map[N] == -1, return N. If Map[N] == N, return N. Otherwise, return findEnd(Map[N]).

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

Finally, run a loop from 0 to N-1. If findEnd(Map[current number]) == 0, increment the answer by 1.

Sample Code－ZeroJudge F677: Disjoint-Set Practice

#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
Tags

Related Posts

Comments