并查集沒有固定的寫法，其可以由個人寫法習慣或具體使用環境的不同而不同，意會此模板再內化自用即可，
B站推薦學習視頻
//開始前必須初始化根節點陣列parent和層數陣列rank
for(int i=0;i<節點數;++i)
{
parent[i]=-1;//或parent[i]=i;
rank[i]=0;
}
//實作并查集首先要實作查找根節點功能
//為了便于表達，寫成函式
int find_root(int x)
{
int x_root=x;//如果不是用-1初始化parent這句不用寫
while(parent[x_root]!=-1
/*如果不是用-1初始化parent改為parent[x_root]!=x_root*/)
{
x_root=parent[x_root];
}
return x_root;
}
//實作并查集需要實作合并兩個點到一個集合的功能
//為了便于描述，寫成函式，回傳1合并成功，回傳0合并失敗
int union_vertices(int x,int y)
{
int x_root=find_root(x);
int y_root=find_root(y);
if(x_root==y_root)
{
//根節點相同，兩個點在一個集合，合并出現環，不能合并
return 0;
}
else {//根節點不同，可以合并，以下結論可畫圖驗證
//兩棵樹層數不等時，層數小的樹合并到層數大的樹上時，
//合并后樹高度未改變，為本次合并的兩棵樹中高度較大的樹的高度
if(rank[x_root]>rank[y_root])
{
parent[y_root]=x_root;
}
else if(rank[y_root]>rank[x_root])
{
parent[x_root]=y_root;
}
//兩顆樹層數相同，哪顆樹的根節點做合并后的根節點都一樣，
//結果都是使合并后樹的高度增1
else {
parent[x_root]=y_root;
++rank[y_root];
}
return 1;
}
}
//使用并查集時，只要有一次合并失敗，就說明圖中有環
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/25257.html
標籤：AI
上一篇：藍牙協議堆疊模組在linux ubuntu 跑藍牙協議堆疊 --傳統藍牙搜索演示以及實作原理
下一篇：鴻蒙OS代碼正式開源