先上一個(gè)圖

再來一個(gè)代碼進(jìn)行解析：

#include <iostream> #include <cstring> using namespace std; int f[50]; void init(int n) { for(int i=1;i<=n;i++) f[i]=i; } int getf(int a) { if(f[a]==a) return a; else { f[a]=getf(f[a]); return f[a]; } } void merge(int a,int b) { int t1,t2; t1=getf(a); t2=getf(b); if(t1!=t2) { f[t1]=t2; } } void print(int n) { for(int i=1;i<=n;i++) cout<<"("<<i<<")"<<f[i]<<" "; cout<<endl; } int main(int argc, const char * argv[]) { int n,m,a,b,sum; sum=0; cin>>n>>m; init(n); for(int i=1;i<=m;i++) { cin>>a>>b; merge(a,b); print(n); } for(int i=1;i<=n;i++) { f[i]=getf(i); } for(int i=1;i<=n;i++) if(f[i]==i) sum++; cout<<sum<<endl; return 0; }

3 3

1 2

2 3

3 1

起先我們先對輸入的這些數(shù)判斷，起先對初始化為自己是自己的父節(jié)點(diǎn)，1 2說明有關(guān)系，然后這里f[1]=2;就是把1作為2的子節(jié)點(diǎn)圖上說明，打叉說明節(jié)點(diǎn)連接到別的節(jié)點(diǎn)上去，在2 3，這里2和3的父節(jié)點(diǎn)都是本身，不相等，就把2連接到3上（即2為3的父節(jié)點(diǎn)），3 1這里3的父節(jié)點(diǎn)是3，1的前一個(gè)節(jié)點(diǎn)是2，但是不是1的父節(jié)點(diǎn)所以要在繼續(xù)找到3，即相等說明不用連。就有最后一個(gè)圖1->2->3,? ? 1 2 的父節(jié)點(diǎn)就是3 說明是一個(gè)集合里面的。

?

哎 ！！！總結(jié)：自己有做過幾道并查集的題目，以為那時(shí)候懂了這個(gè)，沒想到昨晚的一道題目反而從新理解了并查集，刷題刷題。

總結(jié)

以上是生活随笔為你收集整理的关于并查集的个人再次的理解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。