89 lines
2.6 KiB
C++
89 lines
2.6 KiB
C++
#include <iostream>
|
|
#include <vector>
|
|
|
|
/**
|
|
* 带权并查集。权重记录该节点到父节点的边的边权（保证一切根节点权重为 0）
|
|
*/
|
|
class DsuWeighted {
|
|
public:
|
|
using NodeIdx = int;
|
|
|
|
struct Node {
|
|
NodeIdx parent = -1;
|
|
int weight = 0;
|
|
std::size_t size = 1;
|
|
};
|
|
|
|
std::vector<Node> nodes;
|
|
const int groups_amount;
|
|
|
|
explicit DsuWeighted(const std::size_t n, int groups = 2) : nodes(n), groups_amount(groups) {
|
|
for (auto i = 0; i < n; i++) {
|
|
nodes[i].parent = i;
|
|
}
|
|
}
|
|
|
|
NodeIdx find(const NodeIdx x) {
|
|
if (nodes[x].parent == x) { return x; }
|
|
find(nodes[x].parent);
|
|
nodes[x].weight += nodes[nodes[x].parent].weight;
|
|
nodes[x].weight %= groups_amount;
|
|
return nodes[x].parent = find(nodes[x].parent);
|
|
}
|
|
|
|
int get_weight(const NodeIdx x) {
|
|
find(x);
|
|
return nodes[x].weight;
|
|
}
|
|
|
|
void unite(NodeIdx x, NodeIdx y, int weight_delta = 0) {
|
|
auto x_root = find(x), y_root = find(y);
|
|
if (x_root == y_root) { return; }
|
|
if (nodes[x_root].size > nodes[y_root].size) {
|
|
std::swap(x, y);
|
|
std::swap(x_root, y_root);
|
|
weight_delta = -weight_delta;
|
|
}
|
|
nodes[x_root].weight += weight_delta + nodes[y].weight - nodes[x].weight;
|
|
nodes[x_root].weight %= groups_amount;
|
|
nodes[x_root].parent = y_root;
|
|
nodes[y_root].size += nodes[x_root].size;
|
|
}
|
|
};
|
|
|
|
int main() {
|
|
std::ios::sync_with_stdio(false);
|
|
std::cin.tie(nullptr);
|
|
std::cout.tie(nullptr);
|
|
|
|
int test_cases_amount;
|
|
std::cin >> test_cases_amount;
|
|
while (test_cases_amount--) {
|
|
int cases_amount, queries_amount;
|
|
std::cin >> cases_amount >> queries_amount;
|
|
|
|
DsuWeighted dsu(cases_amount, 2);
|
|
while (queries_amount--) {
|
|
char op;
|
|
int case_id_1, case_id_2;
|
|
std::cin >> op >> case_id_1 >> case_id_2;
|
|
case_id_1--, case_id_2--;
|
|
if (op == 'D') {
|
|
dsu.unite(case_id_1, case_id_2, 1);
|
|
} else if (op == 'A') {
|
|
if (dsu.find(case_id_1) != dsu.find(case_id_2)) {
|
|
std::cout << "Not sure yet." << std::endl;
|
|
} else {
|
|
if ((dsu.get_weight(case_id_1) - dsu.get_weight(case_id_2)) % 2 == 0) {
|
|
std::cout << "In the same gang." << std::endl;
|
|
} else {
|
|
std::cout << "In different gangs." << std::endl;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
return 0;
|
|
}
|