并查集
/* * INIT: makeset(n); * CALL: findset(x); unin(x, y); */
const int N = 1010;
struct lset
{
int p[N], rank[N], sz;
void link(int x, int y)
{
if (x == y)
{
return ;
}
if (rank[x] > rank[y])
{
p[y] = x;
}
else
{
p[x] = y;
}
if (rank[x] == rank[y])
{
rank[y]++;
}
return ;
}
void makeset(int n)
{
sz = n;
for (int i = 0; i < sz; i++)
{
p[i] = i;
rank[i] = 0;
}
return ;
}
int findset(int x)
{
if (x != p[x])
{
p[x] = findset(p[x]);
}
return p[x];
}
void unin(int x, int y)
{
link(findset(x), findset(y));
return ;
}
void compress()
{
for (int i = 0; i < sz; i++)
{
findset(i);
}
return ;
}
};
2018.5.11 修改,这是裸的基础并查集