我们四处寻找一个简单的算法，在直径有时很大的图中找到连接的组件（最大的组件有时可以达到1m）。
我们发现了许多非常复杂的MR算法：
- http://codingwiththomas.blogspot.de/2011/04/graph-exploration-with-hadoop-mapreduce.html
- http://blog.piccolboni.info/2010/07/map-reduce-algorithm-for-connected.html
- http://chasebradford.wordpress.com/2010/10/23/mapreduce-implementation-for-union-find/
一个非常简单的算法有什么问题：
- foreach组件，生成flatten（nodes_bag）作为node，node_with_the_smallist_id作为comp_id
- 按节点分组
- 过滤具有多个comp_id的节点，并构建"将大comp_id更新为小comp_id"表
- 将具有大comp_id的所有节点更新为相应的新的小comp_id，并将其标记为dirty
并使用这些脏节点继续进行下一次迭代。。。我们这里缺少什么？
您提出的算法不是二次型的吗？Tarjan的连通分量算法是线性的。
好的。我们不能使用这个非常简单的算法的原因是它有一个错误=构建"将大comp_id更新为小comp_id"阶段可能是递归的。例如，当上一次迭代中有3个组件时：
A->{1,2}
B->{2,3}
C->{3,4}
分组依据和过滤器将为我们构建这个翻译表：
A->B
B->C
这将导致迭代次数在某些情况下是线性的（最大直径）=像这个小例子中的长链需要很长时间才能收敛。