请教大家一道算法题？

資深大佬 : ihourui 5

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 多的时候效率太差，请问一下各位有什么好的算法可以实现吗？谢谢！

大佬有話說 (11)

資深大佬 : 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 就可以线性了。