This documentation is automatically generated by online-judge-tools/verification-helper
#include <vector>
using namespace std;
// ----- UnionFind -----
class UnionFind
{
int N;
vector<int> par;
public:
UnionFind() : N{0} {}
UnionFind(int N) : N{N}, par(N, -1) {}
bool is_same(int x, int y)
{
return root(x) == root(y);
}
bool merge(int x, int y)
{
x = root(x);
y = root(y);
if (x == y)
{
return false;
}
if (par[x] > par[y])
{
swap(x, y);
}
par[x] += par[y];
par[y] = x;
return true;
}
int size(int x)
{
return -par[root(x)];
}
int count_parts()
{
int ans{0};
for (auto i = 0; i < N; i++)
{
if (par[i] < 0)
{
++ans;
}
}
return ans;
}
private:
int root(int x)
{
if (par[x] < 0)
{
return x;
}
return par[x] = root(par[x]);
}
};
#line 1 "DataStructure/UnionFind.cpp"
#include <vector>
using namespace std;
// ----- UnionFind -----
class UnionFind
{
int N;
vector<int> par;
public:
UnionFind() : N{0} {}
UnionFind(int N) : N{N}, par(N, -1) {}
bool is_same(int x, int y)
{
return root(x) == root(y);
}
bool merge(int x, int y)
{
x = root(x);
y = root(y);
if (x == y)
{
return false;
}
if (par[x] > par[y])
{
swap(x, y);
}
par[x] += par[y];
par[y] = x;
return true;
}
int size(int x)
{
return -par[root(x)];
}
int count_parts()
{
int ans{0};
for (auto i = 0; i < N; i++)
{
if (par[i] < 0)
{
++ans;
}
}
return ans;
}
private:
int root(int x)
{
if (par[x] < 0)
{
return x;
}
return par[x] = root(par[x]);
}
};