本文共 2329 字，大约阅读时间需要 7 分钟。

这道题的关键在于利用并查集数据结构来处理动态的合并和查找操作。类型D的消息会给出两个人的组是不同的，这需要用并查集来合并他们的关系，并记录他们的敌人关系。类型A的消息则需要根据当前的状态来判断两个人的组是否相同。

并查集的实现：

处理消息逻辑：

• 类型D [a] [b]：当处理这条消息时，找到a和b的当前根。如果其中一个的敌人已经被设置，则将敌人的关系合并，并更新父节点。同时，标记a和b的敌人关系。
• 类型A [a] [b]：查找a和b的当前根。如果根相同，说明在同一组。如果根不同，检查他们的敌人是否在同一组。如果敌人组不同，则说明在不同的组；否则，无法确定。

代码实现：

#include 
   
    #include 
    
     #define REP(i, s, n) for(int i = s; i <= n; i++)#define MAX_N 100000 + 10using namespace std;int find(int x) {    if(F[x] == x) return x;    return F[x] = find(F[x]);}void Union(int x, int y) {    x = find(x);    y = find(y);    if(x == y) return;    F[y] = x;}int main() {    int T;    scanf("%d", &T);    while(T-- > 0) {        int n, q;        scanf("%d %d", &n, &q);        F = new int[MAX_N];        E = new int[MAX_N];        for(int i=1; i<=n; i++) {            F[i] = i;            E[i] = 0;        }        for(int i=1; i<=n; i++) E[i] = 0;        while(q--) {            char s[3];            scanf("%s", s);            if(s[0] == 'D') {                int x, y;                scanf("%d %d", &x, &y);                if(E[x] == 0 && E[y] == 0) {                    E[x] = y;                    E[y] = x;                } else if(E[x] == 0) {                    E[x] = y;                    Union(x, E[y]);                } else if(E[y] == 0) {                    E[y] = x;                    Union(y, E[x]);                } else if(E[x] != 0 && E[y] != 0) {                    if(E[x] == E[y]) {                        Union(x, E[x]);                        Union(y, E[y]);                    } else {                        Union(x, E[y]);                        Union(y, E[x]);                    }                }            } else if(s[0] == 'A') {                int x, y;                scanf("%d %d", &x, &y);                int fx = find(x);                int fy = find(y);                if(fx == fy) {                    printf("In the same gang.\n");                } else if(E[fx] == E[fy]) {                    printf("In different gangs.\n");                } else {                    printf("Not sure yet.\n");                }            }        }    }    return 0;}
    
   

解释：

• 初始化：每个节点的父节点指向自己，敌人数组初始化为空。
• 类型D处理：将两个节点的敌人关系合并，并更新父节点，使其在同一组。
• 类型A处理：根据当前的父节点和敌人关系判断两个节点的组是否相同。

这种方法确保了在处理大量查询时的高效性，适合题目给定的约束条件。

转载地址：http://tuxfk.baihongyu.com/