G题是并查集吗?
本人的理解:
对于苏醒灵魂的点 ,其能在天亮时停留在点 处,当且仅当在三个次元空间,都存在从点 到点 的路径。
因此对于某个苏醒的点,其在天亮时醒来的方案数,等价于其在天亮时能停留的点数,等价于三个次元空间都连通的点数。
故本人考虑使用并查集,先对于输入的边,分别对三个次元空间使用并查集合并线段两端点;而后扫一遍所有线段的两端点,考虑是否该两端点在三个次元空间都分别同属于一个并查集;若满足分别同属于一个并查集,则用另一个并查集合并两点。
最后求出每个点所在的(最后那一个)并查集大小。
请问有什么问题吗?