并查集80分求调
查看原帖
并查集80分求调
905071
wbs123456楼主2025/1/24 17:17

rt,80分代码:

#include<bits/stdc++.h>
using namespace std;
namespace DSU{
template<typename T>
class disjointSetUnion {
private:
unordered_map<T,T> father;
unordered_map<T,int> Size;
unordered_map<T,T> Minimal;
unordered_map<T,T> Maximal;
unordered_map<T,T> sum;
public:
T find(T x) {
if (father[x] == x)
return x;
else
return father[x] = find(father[x]);
}
bool isSameSet(T x,T y){
return find(x)==find(y);
}
void Union(T x, T y) {
T rx = find(x), ry = find(y);
if (rx != ry) {
if(Size[ry]>Size[rx]){
father[rx] = ry;
Size[ry] += Size[rx];
Minimal[ry]=min(Minimal[ry],Minimal[rx]);
Maximal[ry]=max(Maximal[ry],Maximal[rx]);
sum[ry]+=sum[rx];
}else{
father[ry] = rx;
Size[rx] += Size[ry];
Minimal[rx]=min(Minimal[ry],Minimal[rx]);
Maximal[rx]=max(Maximal[ry],Maximal[rx]);
sum[rx]+=sum[ry];
}
}
}
void Union(pair<T,T> p){
return Union(p.first,p.second);
}
void insert(T x) {
if(Size[x]==0) father[x] = x,Size[x] = 1,Minimal[x]=x,Maximal[x]=x,sum[x]=x;
}
size_t size(T x) {
return Size[find(x)];
}
T minimal(T x) {
return Minimal[find(x)];
}
T maximal(T x) {
return Maximal[find(x)];
}
T Sum(T x) {
return sum[find(x)];
}
disjointSetUnion(){}
disjointSetUnion(T x){
insert(x);
}
disjointSetUnion(vector<T> x){
for(auto i:x) insert(i);
}
};
}
int main(){
DSU::disjointSetUnion<int> ufs;
int n,m;
cin>>n>>m;
ufs.insert(n);
ufs.insert(m);
ufs.Union(n,m);
cout<<ufs.Sum(n);
}
2025/1/24 17:17
加载中...