原题链接题解建桥相当于把区间内的路合并起来，这引导我们用并查集维护可是具体如何实现呢？我们令桥内的所有节点的统一指向最右端点作为首领，然后对于桥内的所有小桥，每次更新完了之后往右边走一格codeclassSolution{public:intfa[2000005];intfinds(intnow){r

Hereisamorestrictlycategorizedlistofalgorithms,withbriefexplanationsforeachcategory:1.SortingAlgorithmsQuickSort:Efficientsortingbypartitioningarraysaroundapivot.MergeSort:Divide-and-conquersortingthatmergessortedsubarr

原题链接题解1.集合+搜索2.把数字看成间隔而不是点3.类似于差分约束，这里的建边意味着相对大小，根据传递性可知，如果ab建边，bc建边，那么ac之间的关系也能确定，可以用搜索维护所以unknown代表两个点没有之间或者间接的边相连，可以用集合维护code#include<bits/stdc++.h>#definel

原题链接题解把这里的数字看成间隔，不要看成点假设已知能和\(l\)组成区间的端点集合\(A\)和以\(r\)组成区间的端点集合\(B\)，这时候加入一个以\(l,r\)为左右端点的区间，那么在加入区间\(l,r\)之后，这两个集合可以合并code#include<bits/stdc++.h>usingnamespacestd

原题链接题解树上只有两种颜色，我们把每种颜色的连通块记录下来，只有当路径两端的点属于同一连通块且颜色与朋友喜欢的不同时输出0code#include<bits/stdc++.h>usingnamespacestd;chars[100005];intfa[100005];intfinds(intnow){returnfa[now]==now?now:fa[now]=fin

原题链接题解把两个含有相同字符的字符串放进一个集合里，这让我想到了并查集这里是线性并集，遍历字符串，对于字符串中出现的字符的集合并到自己身上来code#include<bits/stdc++.h>usingnamespacestd;intocc[30]={0};intfa[200005];intfinds(intnow){returnfa[now]==n

原题链接题解\(a\tob,b\toc,a\toc\)等价于\(a\tob\toc\)\(a\toz,b\toz\)也可以等价于\(a\tob\toz\)花费不变所以是并查集，然后累积建边数量如果\(finds(a)==finda(z)\)代表\(a\)可以通过其他的变化也顺便变成\(z\)code#include<bits/stdc++.h>usingna

原题链接题解抽象化抽象成点和边，对于抹除一个点，判断整个图是否联通等价于建立一个点（被抹除点的前一个点），判断这个点与周围点相连后，累积合并次数是否等于点数减一code#definelllonglong#include<bits/stdc++.h>usingnamespacestd;llfa[200005];llfinds(llnow){ret

原题链接题解，请看题解区第一篇，看一遍就会了code#include<bits/stdc++.h>usingnamespacestd;intfa[400005]={0};intfinds(intnow){returnfa[now]=(fa[now]==now?now:finds(fa[now]));}vector<int>G[400005];intbroke[400005];intBroke[400005]={0};intm

原题链接思路并查集然后看看是否存在上表面联通的洞与下表面联通的洞位于同一集合code#include<bits/stdc++.h>usingnamespacestd;doublen,h,r;intfa[1005];vector<int>up,down;struct{doublex,y,z;}hole[1005];doubledis(inti,intj){returnpo