之前做算法题的时候做过并查集的题,只是针对题目局限的理解了一下并查集的概念,今天又翻了一下算法4这本书,有了一点点更进一步的认识。
其实在做题的时候,忽略了一个并查集的根本问题,所以实际上,在使用并查集解决问题的时候总有一些难受和别扭,思路能找到,但是很不顺畅,今天看过书之后才明白这个不顺畅的点在哪。
并查集,是为了解决连通判断的问题
比如
1000个人,判断两个人是不是朋友或者间接朋友(是否连通)
10000个点,两个点之间是否有通路。
100000000000个数据,要怎么归类。
这事并查集要解决的核心问题,当遇到的问题,需要被抽象为连通性问题时,并查集就有了出场的机会。
过年这七天,针对并查集做一个深刻的学习,顺便也解决了过年七天的日更困扰。
网友评论