bingchaji

初学并查集概念通过管理数组的下标与值实现的树状数据结构若进行路径压缩树状结构会被破坏可体现数据之间的集合关系可实现集合合并与查询。实现步骤1初始化voidinit(intn){for(inti1;in;i){fa[i]i;}}2查找intfind(intx){if(fa[x]x){returnx;}else{returnfa[x]find(fa[x]);//实现路径压缩让查找遍历过的元素全部连接至根元素下}}3合并voidunite(intx,inty){fa[find(x)]find(fa[y]);//把x所在集合的根元素连接到y所在集合的根元素上}合并可以通过按秩合并来优化即通过条件判断始终让更矮的树连接到更高的树上因为合并的过程中被合并的那个树会因为增加了一个根元素而导致深度1若不进行按秩合并可能会出现始终把更高的树合并到较矮的树上深度不断递增的情况大大增加了查找的时间复杂度。应用需要搭配其他数据结构来完成对并查集下标数字的映射即将下标的数字在新的数组或哈希表中存储上对应的具体数据。优化若保留树结构则应将查找函数改为intfind(intx){if(fa[x]x){returnx;}else{returnfind(f[x]);//不实现路径压缩保留树结构}}这样不会破坏树结构但却大大增加了查询的时间最坏情况下时间复杂度达到O(n),而经过路径压缩的查找时间复杂度是O(log n)。