来来 show 智商的来做笔试题

[rootzeal]

这是一道我们公司的笔试题 那天遇到了连我都做不起是不是要被开了呀 各位是时候展现真正的实力了 靠你们了
https://mp.weixin.qq.com/s/ZG90qxnenoJuRUDezNbgEQ

[brainfxxk]

无向图找连通分量？

[AlisaDestiny]

并查集？

[casparchen]

并查集统计森林中树的个数，活着直接遍历搜索。这是个简单题啊

[also24]

第一反应并查集，但是感觉这么常规的题目很没意思阿。

仔细一看题目还贴心的区分了 c p 两类，那应该还有办法优化下效率（只需要重点关注连接了多条道路的城市就够了），不过懒得细想了哈哈哈哈

[mixz]

很简单的题目，也可以用 dfs 套循环来代替并查集。

[RingoTC]

@casparchen 不应该是树吧，是图的连通子图。

[stevenbipt]

第一想法是并查集

[mikeguan]

例子中的 c0 为什么不是独立的

[also24]

@stevenbipt #7 例子是没错的阿

[stevenbipt]

@also24 老铁你可能艾特错人了

[casparchen]

@RingoTC #6 不是说了转成并查集问题么，并查集不是树是什么。

[also24]

@stevenbipt 咦… 我的错我的错… 看来现在手越来越不稳了啊

[yswb]

这个题目内容就有问题吧，图上有 6 条连线，但是数据只给了 5 个关系，按这个数据来看的话 c0 是孤立的了

[necomancer]

嗯……根据这个做个邻接表然后 DFS ？非科班想的笨办法。P.S. 你的数据少一组 [c2, p2] 吧？

[qqor]

404 ？
原来我屏蔽这个网址了，哈！

[rootzeal]

@brainfxxk 对是这个意思 有没有办法在分布式或者 sql 环境下解决这个问题

[zdkk]

@yswb c2 和 c0 少一个关系，不知道是题目这样设计，还是楼主疏忽

[rootzeal]

@zdkk 我得错😂