There are N staff members in the Information Investigation Bureau. The head of the bureau secretly divides these people into two groups, A and B, without informing the others. The cooperation list is then distributed to the group leaders. The cooperation list consists of many pairs, each pair (x, y) indicating that x and y need to work together on a task. It is guaranteed that x and y will not be in group A or group B at the same time.
The group leader accidentally lost the cooperation list, leaving only M pairs remaining. To recover the lost data, the group leader dispatched P investigators, numbered from 1 to P, to investigate the cooperation relationships. Each investigator will return exactly K pairs of data.
Some investigators return data that conflicts with the information held by the group leader (meaning that adding these K pairs to the remaining M pairs in the leader's possession would cause a contradiction in the division of people into groups A and B). Please output the numbers of the investigators who returned erroneous results in ascending order. It is guaranteed that there will be at least one and at most three.
Additionally, it is guaranteed that if the K pairs of results from an investigator do not conflict with the M pairs held by the group leader, then the investigator's data must be consistent with the original division into groups A and 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 |
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