请教大家一道算法题？

[ihourui]

c++里有一堆 pair, 比如<1,2>, <3,2>, <3,6>, <6,3>, <6,4>, <5,8>, <9,8>, <10,12>, <12,11>, 把 pair 里不管第一个还是第二个元素相同的 pair 划分为一组, 最后的结果是[<1,2>, <3,2>, <3,6>,<6,3>, <6,4>], [<5,8>, <9,8>], [<10,12>, <12,11>]，我自己是用循环实现的，但是 pair 多的时候效率太差， 请问一下各位有什么好的算法可以实现吗？谢谢！

[siyemiaokube]

谢不邀，不确定你说的啥

方法一：建图，二元组就是一条边。缺点是不适合动态维护

方法二：hash+并查集。适合动态维护，效率略低。

[luckyrayyy]

把所有 pair 用图来表示，然后判断里面一共有几组连通图？ dfs 搜？

[siyemiaokube]

update：不需要建图，直接把一个 pair<a,b>当成并查集里的 merge （ a，b ）就行了

[xupefei]

一楼说的对。
把 pair 中的每个元素作为 key 建立哈希表，然后用 union-find 。时间复杂度 O(\log n)。

[ksedz]

至少要循环遍历一次的

如果你是指多次操作慢可以考虑加结果缓存或在产生时打标记

[Allianzcortex]

1 楼 + 1，Hash + 并查集，楼主的需求和这道题很相似： https://leetcode-cn.com/problems/baby-names-lcci/

[QingchuanZhang]

就是这个题： https://leetcode-cn.com/problems/most-stones-removed-with-same-row-or-column/

并查集就好了

[lithbitren]

楼里的这两道并查集题的最短 py 解法都是俺写的，时间上一道 100%一道 98%，理论上 c++也可以按照相同原理实现。

[ihourui]

@siyemiaokube 谢谢，我试一下你的做法，非常感谢！

[ihourui]

@luckyrayyy 我就是用 dfs 递归搞的，但是 pair 多的时候时间消耗很大。

[sarvatathagata]

如果没有修改的话，可以做到线性。先与一楼的做法一样 hash，然后对于出现过的每一个 first 元素和每一个 second 元素建虚点，<a,b>和第一类虚点{a}还有第二类虚点{b}连边。然后跑 dfs 就可以线性了。