题目链接： 传送门
#include <cstdio> using namespace std; const int N = 50010; int n, m, ans = 0; int p[N], d[N]; //初始化父结点 void init() { for (int i = 1; i <= n; i++) p[i] = i; } //找到根节点，同时维护边权 int find(int x) { if (p[x] == x) return x; int tmp = find(p[x]); d[x] += d[p[x]]; return p[x] = tmp; } //连接两点之间的捕食关系 void mergeEat(int x, int y) { int px = find(x); int py = find(y); if (px != py) { p[px] = py; d[px] = d[y] +1 - d[x]; } } //连接两个点之间的同类关系 void mergeSame(int x, int y) { int px = find(x); int py = find(y); if (px != py) { p[px] = py; d[px] = d[y] - d[x]; } } int main() { scanf("%d%d", &n, &m); //初始化 init(); while (m--) { int t, x, y; scanf("%d%d%d", &t, &x, &y); //第二种假话x或y大于n if (x > n || y > n) ans++ ; else { int px = find(x), py = find(y); //第一种即x和y同类 if (t == 1) { //先判断此话是否矛盾(具体判断见下方解释) if (px == py && (d[x] - d[y]) % 3) ans++ ; //以同类的方式连接结点 else mergeSame(x, y); } //第二种即x吃y else { //先判断此话是否矛盾(具体判断见下方解释) if (px == py && (d[x] - d[y] - 1) % 3) ans++ ; //以捕食的方式连接结点 else mergeEat(x, y); } } } //最后输出答案 printf("%d\n", ans); return 0; }这道题我用的是带边权的并查集来做的（用拓展域也可以）。带边权的并查集主要思路是，首先创建一个d数组用于维护边权。在find函数中，在找根的同时找到当前点到根节点的边权。而每次我们在查询两点间的关系时都可以通过相对边权（即两个点到根结点的边权只差）来查找。 以这道题为例，这道题的核心问题是如何才能通过边权来找到两个点之间的关系呢？ 这道题的核心思路就是把所有的结点分成三组（及题目中的A，B，C）然后把当前边权求模3，比如当前点的边权求模为0时，该点在组A；当前点的边权求模为1时，该点在组B；当前点的边权求模为2时，该点在组C。这样我们就可以判断当前点所在的组了。因为我们要利用边权求两点间的相对关系，所以我们没必要太专注于当前点到底是A，B，C中的那一组。我们要求的是两点间的相对关系。 那具体的方法就是把他们的相对边权mod3。如果同组则它们的相对边权求应该为0，即(d[x] - d[y]) % 3) == 0；如果是捕食关系，那么它们的相对边权mod3应该还差1，即(d[x] - d[y] - 1) % 3 == 0。根据这一性质，我们就可以判断是否两点同组（或捕食关系），也可以以后这种方式把两点连接起来（连接为同组关系或捕食关系）。 核心思路讲完现在讲讲整体思路，首先按照上面的思路写出find和merge（两种连接方法）函数，然后每次接受操作和x，y。如果x和y大于n则直接记为错误，否则往后如果是操作1，则看这两个点是否已连接，如果未连接则连接，已连接则判断这两点间的关系（具体方法上面讲了），如果矛盾ans++，不矛盾则继续。操作2的操作与操作1基本相似，除了判断条件和连接方法。最后输出答案即可
还有一种用拓展域来做的方法
//用拓展域与来做 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 200010; int p[N], n, m, op, a, b, ans; //初始化父结点 void init() { for(int i = 1; i < N; i++) p[i] = i; } //查找某个点的根结点 int find(int x) { if(p[x] == x) return p[x]; return p[x] = find(p[x]); } //合并两个点所在的集合 void merge(int x, int y) { p[find(x)] = find(y); } int main() { scanf("%d%d", &n, &m); init(); while(m--) { scanf("%d%d%d", &op, &a, &b); //有任何一个数字大于n的情况 if(a > n || b > n) { ans++; continue; } //把点分为三种情况，分别为本身，作为捕食者，作为食物 int as = a, ae = a + n, af = a + n + n; int bs = b, be = b + n, bf = b + n + n; //如果是同类的情况 if(op == 1) { //查看他们之间是否存在捕食的关系 if(find(ae) == find(bs) || find(as) == find(be)) ans++; //查看他们间是否已经合并 else if(find(as) != find(bs)) { //既然他们是同类那么他们的食物和天敌的区间应该是相同的 merge(as, bs); merge(ae, be); merge(af, bf); } } else { //他们间是否为同类或者他们的不是关系是否反过来了 if(find(as) == find(bs) || find(as) == find(be)) ans++; //判断没问题后查看他们之间是否已经合并 else if(find(ae) != find(bs)) { //表示a吃b merge(ae, bs); //表示b被a吃 merge(as, bf); //表示a被b的食物吃（这个关系很重要不要漏掉） merge(af, be); } } } printf("%d\n", ans); return 0; }