void Make_Set() {
for (int i = 0; i <= numberOfVillages + 1; i++) {
set[i] = i;
rank_[i] = 0;
}
}
int Find_Set(int i){
if (set[i] == i)
return set[i];
return Find_Set(set[i]);
}
bool Union(int i, int j){
i = Find_Set(i);
j = Find_Set(j);
if (i == j) return false;
if (rank_[i]>rank_[j]) set[j] = i;
else
{
if (rank_[i] == rank_[j]) rank_[j]++;
set[i] = j;
}
return true;
}
求dalao们帮我看看这段代码大概的逻辑,有点看懵了
void Make_Set() { //设置数组 set从0到numberOfVillages + 1 rank_全是0
for (int i = 0; i <= numberOfVillages + 1; i++) {
set[i] = i;
rank_[i] = 0;
}
}
int Find_Set(int i){ //从数组里找i,默认从 i位开始找,如果不对,看i位的值对应的位对不对。 一直找。
if (set[i] == i)
return set[i];
return Find_Set(set[i]);
}
bool Union(int i, int j){
i = Find_Set(i);
j = Find_Set(j);
if (i == j) return false; //找到的i和j如果相同,就返回false
if (rank_[i]>rank_[j]) set[j] = i; rank里i位大于j位,则set的J位赋值i 否则 如果rank的i位=j位,则rank的j位+1 然后set的i位赋值j 返回true
else
{
if (rank_[i] == rank_[j]) rank_[j]++;
set[i] = j;
}
return true;
}
Make_Set 这个方法是将set[]定义为[0,1,2,3,...,numberOfVillages+1],将rank_[] 定义为[0,0,0.....]
Find_Set就是找从set[i]里面找到一个元素set[i] = i
Union这里运行到i = Find_Set(i);
j = Find_Set(j);这里其实i =set[i],j=set[j]了,后面的就是通过判断rank_[i]是大于还是等于rank[j]给set[i]或者set[j]赋值了
代码都懂,但是逻辑上搞不清啊。。。
这些都是函数实现,博主能把具体的函数应用的代码发一下么