神马作文网北大acm题中有哪些题使用并查集来做的?
来源：学生作业帮 编辑：神马作文网作业帮 分类：综合作业 时间：2024/11/18 13:17:45
北大acm题中有哪些题使用并查集来做的?
请给出每题的ID即可,越多题给出越好.
不需要网址，我需要把题目的ID列出，
请给出每题的ID即可,越多题给出越好.
不需要网址，我需要把题目的ID列出，
POJ 1611 The Suspects 最基础的并查集
POJ 2524 Ubiquitous Religions 最基本的并查集
POJ 1182 食物链 并查集的拓展
注意:只有一组数据;
要充分利用题意所给条件:有三类动物A,B,C,这三类动物的食物链
构成了有趣的环形.A吃B,B吃C,C吃A.也就是说:只有三个group
POJ 2492 A Bug's Life 并查集的拓展
法一:深度优先遍历
每次遍历记录下该点是男还是女,只有:男-〉女,女-〉男满足,否则,找到同性恋,结束程序.
法二:二分图匹配
法三:并查集的拓展:和1182很像,只不过这里就有两组,而1182是三组,1611无限制
POJ 1861 Network == zju_1542 并查集+自定义排序+贪心求"最小生成树"
答案不唯一,不过在ZOJ上用QSORT()和SORT()都能过,在POJ上只有SORT()才能过...
POJ 1703 Find them,Catch them 并查集的拓展
这个和POJ 2492 A Bug's Life很像,就是把代码稍微修改了一下就AC了!
注意：And of course,at least one of them belongs to Gang Dragon,and the same for Gang Snake.就是说只有两个组.
POJ 2236 Wireless Network 并查集的应用
需要注意的地方：1、并查集；2、N的范围,可以等于1001；3、从N+1行开始,第一个输入的可以是字符串.
POJ 1988 Cube Stacking 并查集很好的应用
1、与 银河英雄传说==NOI2002 Galaxy一样；2、增加了一个数组behind[x],记录战舰x在列中的相对位置；3、详细解题报告见银河英雄传说.
JOJ 1905 Freckles == POJ 2560 最小生成树
法一：Prim算法；法二：并查集实现Kruskar算法求最小生成树
POJ 2524 Ubiquitous Religions 最基本的并查集
POJ 1182 食物链 并查集的拓展
注意:只有一组数据;
要充分利用题意所给条件:有三类动物A,B,C,这三类动物的食物链
构成了有趣的环形.A吃B,B吃C,C吃A.也就是说:只有三个group
POJ 2492 A Bug's Life 并查集的拓展
法一:深度优先遍历
每次遍历记录下该点是男还是女,只有:男-〉女,女-〉男满足,否则,找到同性恋,结束程序.
法二:二分图匹配
法三:并查集的拓展:和1182很像,只不过这里就有两组,而1182是三组,1611无限制
POJ 1861 Network == zju_1542 并查集+自定义排序+贪心求"最小生成树"
答案不唯一,不过在ZOJ上用QSORT()和SORT()都能过,在POJ上只有SORT()才能过...
POJ 1703 Find them,Catch them 并查集的拓展
这个和POJ 2492 A Bug's Life很像,就是把代码稍微修改了一下就AC了!
注意：And of course,at least one of them belongs to Gang Dragon,and the same for Gang Snake.就是说只有两个组.
POJ 2236 Wireless Network 并查集的应用
需要注意的地方：1、并查集；2、N的范围,可以等于1001；3、从N+1行开始,第一个输入的可以是字符串.
POJ 1988 Cube Stacking 并查集很好的应用
1、与 银河英雄传说==NOI2002 Galaxy一样；2、增加了一个数组behind[x],记录战舰x在列中的相对位置；3、详细解题报告见银河英雄传说.
JOJ 1905 Freckles == POJ 2560 最小生成树
法一：Prim算法；法二：并查集实现Kruskar算法求最小生成树