1、题目要求：
某学校有N个学生，形成M个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好，形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据“我的朋友的朋友也是我的朋友”这个推论可以得出，如果A和B是朋友，且B和C是朋友，则A和C也是朋友。请编写程序计算最大朋友圈中有多少人。
输入格式:
输入的第一行包含两个正整数N（≤30000）和M（≤1000），分别代表学校的学生总数和俱乐部的个数。后面的M行每行按以下格式给出1个俱乐部的信息，其中学生从1~N编号：
第i个俱乐部的人数Mi（空格）学生1（空格）学生2 … 学生Mi
输出格式:
输出给出一个整数，表示在最大朋友圈中有多少人。
输入样例:
7 4
3 1 2 3
2 1 4
3 5 6 7
1 6输出样例:
4#include <bits/stdc++.h> using namespace std; #define MAXn 30001 int fa[MAXn]; int num[30001]; int Find(int x){ int r=x; while(r!=fa[r]) r=fa[r]; int i=x,temp; while(r!=fa[i]){ temp=fa[i]; fa[i]=r; i=temp; } return r; } void Union(int x,int y){ int fx=Find(x),fy=Find(y); if(fx!=fy){ fa[fx]=fy; num[fy]+=num[fx]; } } int main(){ int n,m,people,first,p; cin>>n>>m; for(int i=0;i<=n;i++) fa[i]=i; for(int i=0;i<=n;i++) num[i]=1; while(m--){ cin>>people; cin>>first; while(--people){ cin>>p; Union(first,p); } } int max=0; for(int i=0;i<=n;i++){ if(num[i] > max) max=num[i]; } cout<<max<<endl; return 0; }
4、“并查集” 说明：
首先本题是属于数据结构中的 “并查集“ 类型的题目，所以要理解本题的代码，我们就要先弄懂什么是并查集。
所以现在，我们先来搞懂 ”并查集“是什么？
顾名思义，”并“就是合并，”查“就是查找，”集“就是集合（元素唯一）。”并查集"主要代码结构有两个函数，一个主函数“，一个函数是 Find(x) ，一个是 Union（x,y）。
将每个集合看成每棵树，用数组 fa[] 来存储各个节点的父节点，fa[i] 表示 i 的父节点。如下图1，fa[2] = 1，fa[3] = 1，fa[4] = 2...... （图论基础）
若每棵树只有一个节点，那么它的父节点就是它自己，即 fa[i] = i，谁和谁都没有关系，如图2。
合并：Union(x,y)
那么我们要怎么把它们建立联系呢，就是把单独的树合并成一颗大的树？
可以令每棵树的根节点都一样，那么它们就合并了，比如要将 图1中的1 和2 合并成一颗树，可以让1成为2的根节点（当然也可以让2成为1的根节点），
即 fa[2] = 1，fa[1] = 1，（fa[1] = 2，fa[2] = 2）这样就变成了图3.
，
若要将3也合并到1那颗树上，如图.可以知道fa[3] = 2， fa[2] = 1，fa[1] = 1，则把3合并过来的表达式：fa[3] = fa[1]，
假设x=2，y=3 ，将2和3合并，则 fa[x] = y ;
这就是将集合合并起来，从上面两个图中我们可以发现若1都是根节点，那么fa[1] = 1，若2是根节点，那么fa[2] = 2，即fa[i] = i 表示此时 i 是这颗树的根节点，
”查“就是查找根节点。
找到根节点有什么用？
查找：Find(x)
找到一颗树的根节点就相当于找到了这颗树的编号，换个说法说就是某个集合的编号，可以知道这个人在哪个集合里。
如下图
我们想找5属于哪颗树，就得一个一个父节点网上找，直到找到根节点 Find(5) = 1才知道5属于上面那颗树。如果我们想找8，那么我们必须找到8的根节点 Find(8) = 6
才知道8属于下面那棵树。
因此函数 Find(x) 就是查找 x的根节点，返回值是一个数（根节点）。
如果我想让5和6成为好朋友呢？只需要在5和6之间画一条线连起来，或者之间让6的父节点之接变成1，这样6就属于5的那颗树啦，如下图
或者这样也行，
即让5的根节点等于6的根节点，因此合并的原理就是：查找x和y 的根节点，fx = Find(x) , fy = Find(y) ；令y的根节点等于x的根节点，Find(fx) = fy。
说到这，想必都清楚”并“和”查“的意思了吧？不知道我说得清楚了没？文案和图有点乱。。。。
还有一点要注意的是，还有个"路径压缩"，这个 “路径压缩” 是啥捏？
举个例子：如下图
假设1是根节点，（不分是否二叉树）， 如果我们要找3的根节点是谁，那么上面图的做法是 fa[3] = 1，查找一次就找到了。而下面图的做法是 fa[3] = 2，不是根节点（怎么判断是不是根节点上文有说），
再查找 fa[2] = 1 找到了，是不是上面图的做法查询的速度会更快一点？如果有n个节点，那么下面图要查找n-1次了，此时效率比较低。所以“路径压缩” 就是要把树（集合）上的
节点都搞成上面图的样子，这样就缩短了查询根节点的路径了。
5、代码解析：
了解了“并查集 " ，那么我们现在就来看看本题的代码怎么实现吧！
#include <bits/stdc++.h> using namespace std; #define MAX 30001 int fa[MAX];//存储父节点 int num[30001];//存储节点数 /*查找根节点*/ int Find(int x){ //找x的根节点 int r=x;//x赋给r，以免中间发生变化后x改变 while(r!=fa[r])//循环直到找到根节点，上文第4点有说例子 r=fa[r];//让r的父节点等于r，直到找到x的根节点,此时就可返回r了，下面是为了压缩路径写的代码 //路径压缩 int i=x,temp;//temp为中间变量 while(r!=fa[i]){//假设链式树，“1---2---3---4” 根节点r=1，x=3，即要把3直接套在1后面，这里上文“路径压缩”有说到。 temp=fa[i];//把3的父节点2赋给temp fa[i]=r;//让3的父节点等于1 i=temp;//把3的父节点2赋给i,继续循环把2的根节点变成1 } return r;//最后返回根节点r } /*合并两个集合*/ void Union(int x,int y){ int fx=Find(x),fy=Find(y);//分别找到x和y的根节点 if(fx!=fy){//如果x和y的根节点不一样，说明两个人不在一棵树上，此时就要合并两个人 fa[fx]=fy;//让y的根节点fy成为x的根节点，两棵树（集合）就合并了 num[fy]+=num[fx];//fy这颗树多加num[fx]个人,num[fx]代表以fx为根节点所在的树上有几个节点 } } int main(){ int n,m,people,first,p; cin>>n>>m; //给每个人编号，并让每个人的父节点都是自己 for(int i=0;i<=n;i++) fa[i]=i; //定义一个num[]数组来存储第i棵树（朋友圈）上有几个节点（人），刚开始都是一个人，所以初始化为1 for(int i=0;i<=n;i++) num[i]=1; //输入数据 while(m--){ cin>>people;//每一行中第一个数是这个圈子有几个人 cin>>first;//第二个数在这里输入，是为了将第一个数作为每一行（每一个圈子）的根，用来标识朋友圈加以区别 while(--people){ cin>>p;//依次输入每个人的编号 Union(first,p);//每输入一个人就合并到第一个人的树（圈子）上，这样每一行的人都代表一个圈子里的人 } } //求出最大的树（圈子）有几个节点（人） int max=0; for(int i=0;i<=n;i++){//人的编号从1~N if(num[i] > max) max=num[i]; } cout<<max<<endl; return 0; }
不知道我讲的明白了没，如果大家还没理解，可以看看这个博客，畅通工程并查集详解。