7-25 朋友圈 (25 分)（详解+并查集的了解和应用）
一：題目
某學(xué)校有N個學(xué)生，形成M個俱樂部。每個俱樂部里的學(xué)生有著一定相似的興趣愛好，形成一個朋友圈。一個學(xué)生可以同時屬于若干個不同的俱樂部。根據(jù)“我的朋友的朋友也是我的朋友”這個推論可以得出，如果A和B是朋友，且B和C是朋友，則A和C也是朋友。請編寫程序計算最大朋友圈中有多少人。
輸入格式:
輸入的第一行包含兩個正整數(shù)N（≤30000）和M（≤1000），分別代表學(xué)校的學(xué)生總數(shù)和俱樂部的個數(shù)。后面的M行每行按以下格式給出1個俱樂部的信息，其中學(xué)生從1~N編號：
第i個俱樂部的人數(shù)Mi（空格）學(xué)生1（空格）學(xué)生2 … 學(xué)生Mi
輸出格式:
輸出給出一個整數(shù)，表示在最大朋友圈中有多少人。
輸入樣例:
7 4
3 1 2 3
2 1 4
3 5 6 7
1 6
輸出樣例:
4
二:思路
利用并查集，求得根節(jié)點的得數(shù)組，再用map<int,int> 來計算當(dāng)中重復(fù)次數(shù)多的個數(shù) 也就是根節(jié)點相同的個數(shù)最大值
三：上碼
#include<bits/stdc++.h> using namespace std;int father[30000]; //int find( int x){ // // while( x != father[x] ) // { // x = father[x]; // } // // return x; //}//壓縮路徑 int find(int x){int r=x;while(father[r]!=r)r=father[r]; //找到他的前導(dǎo)結(jié)點int i=x,j;while(i!=r){ //路徑壓縮算法j=father[i]; //記錄x的前導(dǎo)結(jié)點father[i]=r; //將i的前導(dǎo)結(jié)點設(shè)置為r根節(jié)點i=j;}return r; } void merge(int x,int y) {int a = find(x);//x的根節(jié)點為a int b = find(y);//y的根節(jié)點為bif( a != b )father[b] = a;//那么將b的根節(jié)點 設(shè)為 a }int main() {int N,M;cin >> N >> M;for( int i = 1; i <= N; i++ )father[i] = i; //設(shè)置根節(jié)點為數(shù)組下標(biāo)，另外元素值為索引 for( int j = 0; j < M; j++ ){int num;cin >> num;vector<int>v;for( int k = 0; k < num; k++ ){int numPeople;cin >> numPeople;v.push_back(numPeople); }for( int i = 0; i < num-1; i++ ){if( find(v[i]) != find(v[i+1]) )merge(v[i],v[i+1]);//比如剛開始的 1和2 他們原來的根節(jié)點不同，所以合并 也就是將索引值為2的數(shù)組值改為1 即根節(jié)點值為1 } }map<int,int>m;for( int i = 1; i <= N; i++){m[find(i)]++; //這里是find(i) 不能是father[i] 否則最后一個測試點答案錯誤} map<int,int>:: iterator t;int max = 0;for(t = m.begin(); t!= m.end(); t++){if( max < t->second )max = t->second;}cout << max;}//7 4 //3 1 2 3 //2 1 4 //3 5 6 7 //1 6// 7 4 // 2 1 4 // 3 5 6 7 // 1 6 // 3 1 2 3四：并查集的相關(guān)知識
這道題用到了并查集，所以我就學(xué)了一下并查集，所以把自己的見解也分享給大家（建議 先看視頻 再瀏覽 博客 再自己敲一遍 學(xué)習(xí)效率高而已，我總是亂著來 以為看幾篇博客就會了，其實最后還是老老實實 去B站看大佬講解視頻 才搞懂）
1:并查集
查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，
用于處理一些不相交集合（Disjoint Sets）的合并及查詢問題
1：查詢元素a和元素b是否屬于同一組
2：合并元素a和元素b所在組 （將有相同元素的元素 合并為一個組 ）
3：需要初始化一個數(shù)組存放父節(jié)點，其索引值 代表元素
2：并查集的AC代碼（模板`）
/*并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合（Disjoint Sets）的合并及查詢問題1：查詢元素a和元素b是否屬于同一組2：合并元素a和元素b所在組 （將有相同元素的元素 合并為一個組 ） 3：需要初始化一個數(shù)組存放父節(jié)點，其索引值 代表元素 */#include<bits/stdc++.h> using namespace std;int father[100]; int find( int x){while( x != father[x] ){x = father[x];}return x; } void merge(int x,int y) {int a = find(x);//x的根節(jié)點為a int b = find(y);//y的根節(jié)點為bif( a != b )father[b] = a;//那么將b的根節(jié)點 設(shè)為 a }int main() {//初始化： 我們將每一個結(jié)點的前導(dǎo)結(jié)點設(shè)置為自己，//如果在merge函數(shù)時未能形成連通，將獨立成點for( int i = 0; i < 10; i++ ){father[i] = i;}}上方的find函數(shù) 效率不高，當(dāng)處理大數(shù)據(jù)時，使用并查集查找時，如果查找次數(shù)很多，那么使用樸素版的查找方式肯定要超時。比如，有一百萬個元素，每次都從第一百萬個開始找，這樣一次運算就是106，如果程序要求查找個一千萬次，這樣下來就是1013,肯定要出問題的。
所以有了壓縮路徑的算法（就是一棵樹只有葉節(jié)點）
void merge(int x,int y){int a=find(x);//x的根節(jié)點為aint b=find(y);//y的根節(jié)點為bif(a!=b)//如果a,b不是相同的根節(jié)點，則說明ab不是連通的pre[a]=b;//我們將ab相連 將a的前導(dǎo)結(jié)點設(shè)置為b }如有疑問 請留言！ 加油陌生的你
總結(jié)
以上是生活随笔為你收集整理的7-25 朋友圈 (25 分)（详解+并查集的了解和应用）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
