這是樸素查找的代碼,適合數(shù)據(jù)量不大的情況：
int findx(int x)
{
int r=x;
while(parent[r] !=r)
r=parent[r];
return r;
}
下面是采用路徑壓縮的方法查找元素：
int find(int x) //查找x元素所在的集合,回溯時壓縮路徑
{
if (x != parent[x])
{
parent[x] = find(parent[x]); //回溯時的壓縮路徑
} //從x結(jié)點搜索到祖先結(jié)點所經(jīng)過的結(jié)點都指向該祖先結(jié)點
return parent[x];
}
上面是一采用遞歸的方式壓縮路徑， 但是，遞歸壓縮路徑可能會造成溢出棧，我曾經(jīng)因為這個RE了n次，下面我們說一下非遞歸方式進行的路徑壓縮：
int find(int x)
{
int k, j, r;
r = x;
while(r != parent[r]) //查找跟節(jié)點
r = parent[r]; //找到跟節(jié)點，用r記錄下
k = x;
while(k != r) //非遞歸路徑壓縮操作
{
j = parent[k]; //用j暫存parent[k]的父節(jié)點
parent[k] = r; //parent[x]指向跟節(jié)點
k = j; //k移到父節(jié)點
}
return r; //返回根節(jié)點的值
}
