网站建设进项填那个服务,外贸婚纱网站 侵权,建手机网站怎么收费,网站开发项目扶持政策有哪些一#xff1a;题目
某学校有N个学生#xff0c;形成M个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好#xff0c;形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据“我的朋友的朋友也是我的朋友”这个推论可以得出#xff0c;如果A和B是朋友#xff0…一题目
某学校有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
二:思路
利用并查集求得根节点的得数组再用mapint,int 来计算当中重复次数多的个数 也就是根节点相同的个数最大值
三上码 #includebits/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 rx;while(father[r]!r)rfather[r]; //找到他的前导结点int ix,j;while(i!r){ //路径压缩算法jfather[i]; //记录x的前导结点father[i]r; //将i的前导结点设置为r根节点ij;}return r;
} void merge(int x,int y)
{int a find(x);//x的根节点为a int b find(y);//y的根节点为bif( a ! b )father[b] a;//那么将b的根节点 设为 a }int main()
{int N,M;cin N M;for( int i 1; i N; i )father[i] i; //设置根节点为数组下标另外元素值为索引 for( int j 0; j M; j ){int num;cin num;vectorintv;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[i1]) )merge(v[i],v[i1]);//比如刚开始的 1和2 他们原来的根节点不同所以合并 也就是将索引值为2的数组值改为1 即根节点值为1 } }mapint,intm;for( int i 1; i N; i){m[find(i)]; //这里是find(i) 不能是father[i] 否则最后一个测试点答案错误} mapint,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 四并查集的相关知识
这道题用到了并查集所以我就学了一下并查集所以把自己的见解也分享给大家建议 先看视频 再浏览 博客 再自己敲一遍 学习效率高而已我总是乱着来 以为看几篇博客就会了其实最后还是老老实实 去B站看大佬讲解视频 才搞懂
1:并查集
查集是一种树型的数据结构 用于处理一些不相交集合Disjoint Sets的合并及查询问题 1查询元素a和元素b是否属于同一组 2合并元素a和元素b所在组 将有相同元素的元素 合并为一个组 3需要初始化一个数组存放父节点其索引值 代表元素
2并查集的AC代码模板
/*并查集是一种树型的数据结构用于处理一些不相交集合Disjoint Sets的合并及查询问题1查询元素a和元素b是否属于同一组2合并元素a和元素b所在组 将有相同元素的元素 合并为一个组 3需要初始化一个数组存放父节点其索引值 代表元素
*/#includebits/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的根节点为a int b find(y);//y的根节点为bif( a ! b )father[b] a;//那么将b的根节点 设为 a }int main()
{//初始化 我们将每一个结点的前导结点设置为自己//如果在merge函数时未能形成连通将独立成点for( int i 0; i 10; i ){father[i] i;}}上方的find函数 效率不高当处理大数据时使用并查集查找时如果查找次数很多那么使用朴素版的查找方式肯定要超时。比如有一百万个元素每次都从第一百万个开始找这样一次运算就是106如果程序要求查找个一千万次这样下来就是1013,肯定要出问题的。
所以有了压缩路径的算法就是一棵树只有叶节点
void merge(int x,int y){int afind(x);//x的根节点为aint bfind(y);//y的根节点为bif(a!b)//如果a,b不是相同的根节点则说明ab不是连通的pre[a]b;//我们将ab相连 将a的前导结点设置为b
}如有疑问 请留言 加油陌生的你
