并查集模版（Java）
2021-02-08 12:18
标签：init nbsp find for union == class ini merge 并查集模版（Java） 标签：init nbsp find for union == class ini merge 原文地址：https://www.cnblogs.com/zhihaospace/p/12770969.html并查集模版（Java）
初始化，找集合老大，合并集合
public class UnionFind {
public int[] parent;
public int n,m,sum;
//开始时每个集合只有自己，所以集合老大也是自己
public void Init()
{
for(int i = 1;i )
parent[i] = i;
return;
}
//获得该集合的老大，带路径压缩
public int get_boss(int v)
{
if(parent[v] == v)
return v;
else
{
parent[v] = get_boss(parent[v]);
return parent[v];
}
}
//合并两个集合
public void Merge(int v,int u)
{
int t1 = get_boss(v);
int t2 = get_boss(u);
parent[t2] = t1;
return;
}
}