並查集 親戚

2022-11-24 17:41:17 字數 3241 閱讀 6918

廢話不多說,直接看題:

一看這道題,我就有了思路:既然這道題身在圖論板塊,那麼就要用圖的儲存、操作方法來解決,先開一個二維陣列a[20001][20001],把初值儘可能賦大,再輸入資料,並建立關係,然後用floyed演算法,雖然不用求最短路徑,但是至少能知道兩人的關係能否通過中繼聯通,如果結果正常(即a[i][j]!=999999),則輸出“yes”,否則輸出“no”。

**如下:

#includeusing

namespace

std;

int a[20001][20001],n,m,q;int

x,y;

intmain()

for(int i=1;i<=n;i++)

a[i][i]=0;//

自己和自己當然不是親戚

for(int i=1;i<=m;i++)

for(int k=1;k<=n;k++)

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

cin>>q;

while(q--)

return0;

}

可是結果卻不容樂觀,花式錯誤:執行超時,執行錯誤,記憶體超限。通過這道題我明白了電腦記憶體有多麼脆弱,才4*10^8個數,我平時十分珍惜空間大小,每一次都開小陣列,難得浪一次,竟然爆空間了。我仍不死心,又換成深搜試了試,結果連樣例都過不了~~,**就不奉上了;後來我有惡補比floyed演算法快的其他最短路徑演算法(如dijkstra),發現時間複雜度也好不到哪去。後來回頭一看題,竟然關係就有100,0000個,詢問有10,0000次,這是讓我o(n)做完嗎,還要用一維陣列,後來聽說要用並查集。

那麼並查集是什麼?這並查集得分開看每一個字;前兩個字“並”和“查”都是並查集的基本操作,稍後自然會說;“集”則代表這些數是一個個集合。“天生我才必有用”,並查集比起陣列來說,更節省空間,二維陣列10000*10000就爆了,怎能容得下這道題的資料範圍呢?而並查集用的只是一維陣列;而且並查集比起floyed演算法來說,時間複雜度也只有o(n),比floyed o(n^3)好多了。

接下來就以此題為例,介紹一下並查集的基本操作

1)初始化並查集:把每一個資料都先初始成一個單獨的集合;

2)查詢:不斷遞迴/迴圈找到指定資料的父節點,直到找到其祖先節點,其中並查集陣列每一元素儲存的是其父節點編號,祖先節點滿足無父節點,也就是其儲存值仍為初始化時的值,即其編號等於其儲存的值(因為初始化時為了分成不同集合把儲存值賦成其編號);祖先節點並非真的是祖先,其實就是一個標誌,只要值為同一祖先節點編號的元素,都能判斷他們在同一集合中,節省了時間;

3)合併:如果兩人祖先不同,且資料給出他們有親緣關係,就可以將他們合併到同一祖先下;

4)判斷元素是否在同一集合中:判斷二人祖先是否相同,如果相同,則在同一集合內;否則在不同集合。

廢話不多說,為了更好理解,特呈上手寫模板,可以與上文結合看:

#includeusing

namespace

std;

int a[20001

],n,m,x,y,q,x2,y2;

void setup()//

初始化並查集

}int find(int x)//

查詢祖先

void mix(int x,int y)//

合併至同一集合

bool is_relative(int x,int y)//

判斷是否有親屬關係

intmain()

cin>>q;

while(q--)

return0;

}

要ac**的同志切勿貼上,別說我沒說過,這只是個模板。小編習慣用cin,cout再加上多次使用函式,會使速度變慢,但是改過之後發現仍不能過,**就算了,於是又研究並查集的優化方法,提升速度,常規優化方法如下:

如圖所示左圖為路徑壓縮前的親戚關係圖,要確定4和6有無親戚關係則需要浪費更多的時間;但右圖是壓縮路徑後的親戚關係圖,能很好地表現出各節點到祖先節點的關係,查詢次數也由此減少。但路徑壓縮的弊端也顯露出來,這樣雖然能表現出各節點和祖先節點的關係,但卻破壞了原本的結構,無法判斷各節點到父節點的直接關係,在個別題目不能使用。

2)按秩合併:這個優化方法既麻煩又不怎麼常見,有兩種,按大小合併和按深度合併,大小合併很簡單,小的合到大的集合中唄;深度合併則考慮的更多,將關係當成樹,把深度小的合併到深度大的上。優點是既能節約時間還能保留好原有關係,但是沒有路徑壓縮快,此題不宜用,也就不詳解了(其實是小編不太會),知道思想就行。

優化之後就大功告成了,小編心中尚存一絲僥倖,據說“std::ios::sync_with_stdio(false);可以使cin,cout和scanf,printf速度相差無幾”,這是在《資訊學奧賽一本通》上看到的,應該挺有用的吧,小編試了一下,切,還相差無幾,簡直和原來一樣,依舊是四個測試點沒過超時,最終全部改成scanf,printf就通過了。行了,不說了,**勝於雄辯,ac**呈上:

#includeusing

namespace

std;

int a[20001

],n,m,sum,p,q;

/*void setup() //初始化每一個集合 }*/

int find(int x)//

不斷尋找父節點+路徑壓縮

/*void mix(int x,int y)//合併各個集合

*//*

bool is_relative(int x,int y)//判斷是否同一祖先,是否在同一集合

*/int

main()

for(int i=1;i<=m;i++)

scanf("%d

",&sum);

while(sum--)

return0;

}

社交叢集 並查集

當你在社交網路平臺註冊時,一般總是被要求填寫你的個人興趣愛好,以便找到具有相同興趣愛好的潛在的朋友。一個 社交叢集 是指部分興趣愛好相同的人的集合。你需要找出所有的社交叢集。輸入在第一行給出一個正整數 n 為社交網路平臺註冊的所有使用者的人數。於是這些人從 1 到 n 編號。隨後 n 行,每行按以下...

並查集(初步)

並查集可以查詢某個是否在一個集合裡,而且可以把兩個或以上的集合合併起來。比如有三個集合,其中1和5在一個集合裡2和11不在一個集合裡。經典的題目 n個人,有m對關係,如果a和b是親戚,b和c是親戚,則a和c也是親戚,求有多少組親戚。描述的不是很好,看例子吧。假設有5個人,1和2是親戚,2和3是親戚,...

Algorithm 並查集

並查集 主要解決圖的連通性問題,比如 1 隨意給你兩個點,讓你判斷它們是否連通 2 問你整幅圖一共有幾個連通分支 初始化 void init int size 非遞迴 int find int x 查詢根節點 return r void join int x,int y 判斷x y是否連通 遞迴法 ...