其实在做题目的时候,这个并查序主要就是两个函数的应用,模版提吧
1:一个数找出该点的父亲节点
2:合并根节点
不过在这之前我们必须做好初始化的工作
int father[1000],fatherson[1000] // 这里随便取数据,自己看题目的要求
void init(int n)
{
for(int i=0;i<=n;i++)
{
father[i]=i; // 先定义每个节点的父亲都为自己
fatherson[i]=1; // 这个数组要不要,要看题目的具体情况
}
}
// 现在是找到自己的父亲节点了
int getfather(int n)
{
// 这是法1:数据量很大的话,不会发生堆栈溢出错误的
while(n!=father[n])
n=father[n];
return n;
// 法2:
if(n!=father[n]
father[n]=getfather(father[n]);
return father[n];
}
void Union(int x,int y)
{
int rootx=getfather(x);
int rooty=getfather(y);
// 这是其中的一种模式
// ------------------------------------------------------------------------
if(rootx==rooty)
// 说明了这是一个环
return ;
else
{
if(fatherson[rootx]>=fatherson[rooty]
{
father[rooty]=rootx;
fatherson[rootx]+=fatherson[rooty];
}
else
{
father[rootx]=rooty;
fatherson[rooty]+=fatherson[rootx];
}
}
// 第二种模式
{
if(rootx!=rooty)
father[rootx]=rooty; // 这就是两个树开始合并;
}
}