简答题
偏难
#7238
发现它,抓住它 一个城市中有两个犯罪团伙A和B,你需要帮助警察判断任意两起案件是否是同一个犯罪团伙所为,警察所获得的信息是有限的。假设现在有N起案件(N<=10…
发现它,抓住它
一个城市中有两个犯罪团伙A和B,你需要帮助警察判断任意两起案件是否是同一个犯罪团伙所为,警察所获得的信息是有限的。假设现在有N起案件(N<=100000),编号为1到N,每起案件由团伙A或团伙B所为。你将按时间顺序获得M条信息(M<=100000),这些信息分为两类:
D [a] [b]
其中[a]和[b]表示两起案件的编号,这条信息表明它们属于不同的团伙所为
A [a] [b]
其中[a]和[b]表示两起案件的编号,这条信息需要你回答[a]和[b]是否是同一个团伙所为
注意你获得信息的时间是有先后顺序的,在回答的时候只能根据已经接收到的信息做出判断。
时间限制:1000
内存限制:65536
输入
第一行是测试数据的数量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.
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
using namespace std;
template <class T> struct DisjointSet {
int *parent;
T *data;
map<T, int> m;
int capacity;
int size;
DisjointSet(int max = 1000) {
capacity = max;
size = 0;
parent = new int[max + 1];
data = new T[max + 1];
}
~DisjointSet() {
delete[] parent;
delete[] data;
}
bool insert(T x) {
if (size == capacity)
return false;
size++;
data[size] = x;
parent[size] = -1;
m[x] = size;
return true;
}
int getIndex(T x) {
for (int i = 1; i <= size; i++)
if (data[i] == x)
return i;
return -1;
}
int find(T x) {
typename map<T, int>::iterator it;
it = m.find(x);
if (it == m.end())
return -1;
int i, rt;
i = rt = it->second;
while (parent[rt] > 0)
rt = parent[rt];
return rt;
}
void unionSet(T x, T y) {
int rx, ry;
rx = find(x);
ry = find(y);
if (rx == -1 || ry == -1)
return;
if (rx == ry)
return;
if (parent[rx] < parent[ry]) {
parent[rx] += parent[ry];
parent[ry] = rx;
} else {
parent[ry] += parent[rx];
parent[rx] = ry;
}
find(x);
find(y);
}
};
int main() {
int t;
cin >> t;
while (t--) {
DisjointSet<int> s;
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
s.insert(i);
for (int i = 1; i <= m; i++) {
int a, b;
char c;
cin >> c >> a >> b;
if (c == 'D')
s.unionSet(a, b);
else {
if (s.find(a) != s.find(b))
cout << "Not sure yet.";
else if (s.parent[a] == s.parent[b])
cout << "In the same gang.";
else
cout << "In different gangs.";
cout << endl;
}
}
}
return 0;
}</pre>
这道题暂未补解析。