ZeroJudge G598: Investigation Pair

情報調查局內有 N 個工作人員，調查局負責人將這些人秘密分成兩組 A 和 B 並不讓其他人知道，並將合作名單分配給組長，合作名單是由很多個 pair 組成，每個 pair (x, y) 代表 x 和 y 需要合作完成任務，並且保證 x 和 y 不會同時在 A 組或是同時在 B 組。

組長不小心將這個合作名單分配遺失，僅剩下其中 M 個 pair，為了要復原這些失去的資料，組長派出了另外 P 個調查員編號 1 到 P 去調查這個合作關係，每一個調查員都會回傳恰好 K 個 pair 的資料回來。

有些調查員回傳的資料和組長手上的資料會產生矛盾 (意即加上這 K 個 pair 和組長手上存留的 M 個 pair 會使得這些人是被分成 A、B 兩組這件事產生矛盾)，請將回傳錯誤結果的調查員編號由小到大輸出出來，保證至少一個且最多三個。

另外保證若調查員的 K 個 pair 的結果和組長存留的 M 個 pair 不會產生矛盾，則保證調查員的資料一定和原本 A、B 分組吻合。

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The first line outputs two positive integers, N and M.
The second line contains 2*M non-negative integers, forming M pairs, indicating the M pairs that are currently retained.
The third line contains two positive integers, P and K. Following this, there are P lines, each containing 2*K non-negative integers, with each pair representing the K pairs found by a specific investigator.		Output the investigator numbers that would cause a contradiction in ascending order, with each number on a separate line.
7 5
0 1 0 2 1 3 2 3 4 5
2 3
0 6 2 4 3 6
0 6 0 3 3 5		2
5 2
0 3 2 3
3 2
0 2 2 4
0 1 1 2
3 4 2 4		1
3
ZeroJudge G598 Sample Test Cases

Thought Process

Use the union-find (disjoint-set) method for storing data. When receiving the 2*M pairs, run a function to update the data in two global arrays: friends and enemies. These arrays represent each person's teammates and the people in the other group, respectively. Initially, set both arrays to -1 from 0 to N-1.

If, when entering the function, the data for both people in the friends array is -1, it means neither person has been judged yet. So, set each person's friends to themselves and enemies to the other person. If the data for both people in the friends array is not -1, it means both people have already been judged. In this case, update all friends and enemies of both people to new friends and enemies using recursion. If one person has data and the other is -1, set the friends of the person without data to the root of the other person's enemies, and set the enemies to the root of the other person's friends.

When checking if the new pair is correct, data validation is also required. Therefore, you can declare two new arrays, newFriend and newEnemy, and copy the data from friends and enemies into them. When receiving a new pair to be checked, the procedure is similar to the one described above, except that if both newFriend and newEnemy for the two individuals have already been judged, no further judgment is needed. After running the function, check whether newFriend[a] is equal to newFriend[b].

Sample Code－ZeroJudge G598: Investigation Pair

#include <iostream>
using namespace std;

int friends[100000] = {}, enemies[100000] = {};
int newFriend[100000] = {}, newEnemy[100000] = {};

int findEnd(const int N) {
    if (N == -1 || friends[N] == -1) return -1;
    if (friends[N] == N) return N;
    return findEnd(friends[N]);
}

int newFind(const int N) {
    if (N == -1 || newFriend[N] == -1) return -1;
    if (newFriend[N] == N) return N;
    return newFind(newFriend[N]);
}

void meet(const int target, const int value) {
    if (friends[target] == target) {
        friends[target] = value;
        return;
    }
    meet(friends[target], value);
    friends[target] = value;
}

void kill(const int target, const int value) {
    if (enemies[target] == target) {
        enemies[target] = value;
        return;
    }
    meet(enemies[target], value);
    enemies[target] = value;
}

void people(const int a, const int b) {
    if (friends[a] == -1 && friends[b] == -1) {
        friends[a] = a;
        friends[b] = b;
        enemies[a] = b;
        enemies[b] = a;
    }
    else if (friends[a] != -1 && friends[b] != -1) {
        meet(a, findEnd(enemies[b]));
        meet(b, findEnd(enemies[a]));
        kill(a, findEnd(b));
        kill(b, findEnd(a));
    }
    else {
        if (friends[a] == -1) {
            friends[a] = findEnd(enemies[b]);
            enemies[a] = findEnd(b);
        }
        else {
            friends[b] = findEnd(enemies[a]);
            enemies[b] = findEnd(a);
        }
    }
}

void check(const int a, const int b) {
    if (newFriend[a] == -1 && newFriend[b] == -1) {
        newFriend[a] = a;
        newFriend[b] = b;
        newEnemy[a] = b;
        newEnemy[b] = a;
        return;
    }
    if (newFriend[a] != -1 && newFriend[b] != -1) return;
    if (newFriend[a] == -1) {
        newFriend[a] = newFind(newEnemy[b]);
        newEnemy[a] = newFind(b);
        return;
    }
    newFriend[b] = newFind(newEnemy[a]);
    newEnemy[b] = newFind(a);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, M;
    cin >> N >> M;
    for (int i = 0; i<N; i++) {
        friends[i] = -1;
        enemies[i] = -1;
    }
    for (int i = 0; i<M; i++) {
        int a, b;
        cin >> a >> b;
        people(a, b);
    }
    int P, K;
    cin >> P >> K;
    for (int i = 1; i<=P; i++) {
        bool window = false;
        for (int j = 0; j<N; j++) {
            newFriend[j] = -1;
            newEnemy[j] = -1;
            if (friends[j] != -1) newFriend[j] = friends[j];
            if (enemies[j] != -1) newEnemy[j] = enemies[j];
        }
        for (int j = 0; j<K; j++) {
            int a, b;
            cin >> a >> b;
            if (window) continue;
            check(a, b);
            if (newFind(a) == newFind(b)) {
                window = true;
            }
        }
        if (window) cout << i << "\n";
    }
}

//ZeroJudge G598
//Dr. SeanXD
Tags

Related Posts

Comments