A40944. 发现它，抓住它
填空题
困难
知识点
题目描述
发现它，抓住它
题目描述
一个城市中有两个犯罪团伙A和B，你需要帮助警察判断任意两起案件是否是同一个犯罪团伙所为，警察所获得的信息是有限的。假设现在有N起案件（N<=100000），编号为1到N，每起案件由团伙A或团伙B所为。你将按时间顺序获得M条信息（M<=100000），这些信息分为两类：
D [a] [b]
其中[a]和[b]表示两起案件的编号，这条信息表明它们属于不同的团伙所为
A [a] [b]
其中[a]和[b]表示两起案件的编号，这条信息需要你回答[a]和[b]是否是同一个团伙所为
注意你获得信息的时间是有先后顺序的，在回答的时候只能根据已经接收到的信息做出判断。
输入
第一行是测试数据的数量T（1<=T<=20）。 每组测试数据的第一行包括两个数N和M，分别表示案件的数量和信息的数量，其后M行表示按时间顺序收到的M条信息。
输出
对于每条需要回答的信息，你需要输出一行答案。如果是同一个团伙所为，回答"In the same gang.“，如果不是，回答"In different gangs.”，如果不确定，回答”Not sure yet."。
样例输入
1
5 5
A 1 2
D 1 2
A 1 2
D 2 4
A 1 4
样例输出
Not sure yet.
In different gangs.
In the same gang.
参考答案
#include <assert.h>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include<vector>
using namespace std;
//带权并查集：本质是维护“菊花圈”，得到同一个参考点root，在查询的时候之间看本点与参考点的关系
// 主要工作是，讨论子父爷三代的关系：由子父、父爷 ->子爷。进一步，通过信号门得出公式。
// find在原本的职责上，还要维护re数组，替换为子爷关系。
// *****血的教训：先必须find递归,以确保父是第二节点，再维护re数组
// union取消重量权衡规则，维护re数组，考虑r1与r2之间的关系，通过信号门得出公式。
//#define DEBUG
class UFS {
public:
vector<int>fa;//father
vector<int>re;//relationship between child and father
int N;
UFS(int n) :N(n+1){
fa.push_back(0);
for (int i = 1; i <= n; i++)
fa.push_back(i);
re.resize(n + 1, 0);
}
int Find(int a) {
if (fa[a] == a)return a;
int end = Find(fa[a]);//注意必须先确保fa[a]是第二节点，不能放到返回值
re[a] = (re[a] + re[fa[a]]) % 2;
return fa[a] =end ;
}
void Union(int a, int b) {
int r1 = Find(a);
int r2 = Find(b);
fa[r1] = r2;
re[r1] = (re[a] + re[b] + 1) % 2;
}
#ifdef DEBUG
void dbg_printf() {
cout << endl << "----------DEBUG-----------" << endl;
for (int i = 0; i < N; i++) {
if (fa[i] > 9&&i<=9)cout << " ";
cout << i << " ";
}
cout << endl;
for (int e : fa)cout << e << " ";
cout << endl;
for (int i = 0; i < N; i++) {
if (fa[i] > 9)cout << " ";
cout << re[i] << " ";
}
cout << endl;
cout << "NEXT :" << endl << endl;
//cout << endl << "----------DEBUG-----------" << endl;
}
#endif
};
int main() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
UFS prime(n);
while (m--) {
char op;
int a, b;
cin >> op >> a >> b;
int r1, r2;
switch (op)
{
case 'A':
r1 = prime.Find(a);
r2 = prime.Find(b);
if(r1!=r2)
cout << "Not sure yet." << endl;
else {
if (prime.re[a] == prime.re[b]) {
cout << "In the same gang." << endl;
}
else {
cout << "In different gangs." << endl;
}
}
break;
case 'D':
prime.Union(a, b);
break;
default:
break;
}
#ifdef DEBUG
prime.dbg_printf();
#endif
}
}
cout << endl;
}
上一题
下一题