1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class UnionFind{
vector<int> pa;
vector<int> sz;
public:
int cc;
UnionFind(int n):pa(n),sz(n,1),cc(n){
ranges::iota(pa,0);
}
int find(int x){
return pa[x]==x?x:pa[x]=find(pa[x]);
}
void merge(int x,int y){
x=find(x),y=find(y);
if(x==y){
return ;
}
if(sz[x]>sz[y]){
swap(x,y);
}
pa[x]=y;
sz[y]+=sz[x];
sz[x]=sz[y];
--cc;
}
bool isSame(int x,int y){
return find(x)==find(y);
}
};
|