T1.relation(亲戚)

题意:给定一些人是亲戚的关系,并询问某两人是不是亲戚
分析:利用并查集维护每个亲戚集合。


T2.gangs(黑社会团伙)

题意:我的朋友的朋友是我的朋友,我的敌人的敌人是我的朋友。现在给出一些人的关系,求最多存在多少组朋友(单独的人也是一组朋友)
思路:这道题有多种理解,按照“朋友的敌人是敌人,敌人的朋友也是敌人”的理解,我们可以用带权并查集做。


T3.filling(矩形填补)

题意:平面上的边平行于坐标轴的矩形,如果三个角上有黑点,那么将第四个角也染成黑点。现在给出一开始的黑点,求最后平面上有多少个点。
分析:注意到最后形成的点集一定为几个互相没有公共点的矩形的并(这里的矩形包括33,34等的内部有多个点的矩形)。为什么会这样呢?把每个点所在的横线和竖线画出来自然就清楚了。经过分析,我们得出以下结论:
1.一个点可以将它所在的横线和竖线连接起来。
2.两个已经被连接起来的线的交点一定是一个黑点。
所以我们只需要维护有多少横线竖线被点连接在一起。这个利用并查集可以轻松完成。


T4.game(格子游戏)

题意:两位大爷在n*n的棋盘上连线,两人轮流连接一条棋盘上的单位长度的边,给出每一步他们连接的起始点坐标和连接方向,求谁先连出一个环。
分析:并查集维护连通性。


T5.lyp(打怪兽)

题意:有n个怪兽,不停给出如下两个操作:
1 a b c:告诉你a怪兽比b怪兽强c
2 a b:询问a和b谁强。如果一样强或不知道,就输出0
分析:带权并查集维护每个怪兽比所在根节点的怪兽强多少。