kuangbin 专题五：并查集食物链_综合

题目链接：
传送门

#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大于nif (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吃yelse{
    //先判断此话是否矛盾(具体判断见下方解释)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基本相似，除了判断条件和连接方法。最后输出答案即可

kuangbin 专题五：并查集 食物链

kuangbin 专题五：并查集食物链