本文主要是介绍P2024 [NOI2001] 食物链 带权并查集 循环关系，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
P2024 [NOI2001] 食物链 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
本文学习自：
题解 P2024 【食物链】 - RE: 从零开始的异世界信竞生活 - 洛谷博客 (luogu.com.cn)
————
关系并查集其实就是在普通并查集的基础上额外开个数组re，用来表示每个点与其根节点的关系。
这个其实很好理解。设0为同类，1为该点吃根节点，2为根节点吃该点。
难处理的就是合并，以及压缩并查集时，re关系数组如何处理。
只需理解这个图：
为什么有这个等式，其实这个等式左右两边表示的都是A与F2的关系 。（A到F2的两条路径和）
再结合关系是循环的（A吃B，B吃C，C吃D，那么A和D就是同类，构成循环了）。
然后就是注意，减法可能减负的，可以加个模数再取模。
代码：
两个find，第一个是压缩时，循环处理re关系数组
第二个注释掉的是递归法，回溯的时候处理re关系数组
int fa[50005];
//带权并查集
int rela[50005];void init(int _size)
{for (int i = 0; i <= _size; i++)fa[i] = i;
}
int find(int aim)
{int cur = aim;int sum = 0;while (fa[aim] != aim){sum += rela[aim];//存aim = fa[aim];}while (fa[cur] != cur){int tmp = cur;cur = fa[cur];fa[tmp] = aim;sum -= rela[tmp];rela[tmp] = (sum+rela[tmp]) % 3;}return aim;
}
//int find(int aim)//从根往下更新
//{
// int father = fa[aim];
// if (fa[aim] == aim)
// return aim;
// fa[aim] = find(father);
// rela[aim] = (rela[aim] + rela[father]) % 3;
// return fa[aim];
//}
void join(int a, int b,int op)
{int oa = a, ob = b;a = find(a);b = find(b);fa[a] = b;rela[a] = (op + rela[ob] - rela[oa]+3)%3;//只处理祖先就好了，其余在压缩的时候处理//并查集就是合并根
}void solve()
{int n, k;cin >> n >> k;init(n);int op, a, b;int ans = 0;for (int i = 1; i <= k; i++){cin >> op >> a >> b;if (a > n || b > n){ans++;continue;}if (op == 1){if (find(a) == find(b)){if(rela[a] != rela[b])ans++; }else{join(a, b,0);}}else{if (a == b){ans++;continue;}//如果在一个集合中，要判断关系是否正确if (find(a) == find(b)){if (rela[a] != (1 + rela[b]) % 3){ans++;}}elsejoin(a, b,1);}}cout << ans << endl;
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int t = 1;//cin >> t;while (t--){solve();}return 0;
}这篇关于P2024 [NOI2001] 食物链 带权并查集 循环关系的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
