关键词：
某学校有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
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4
5 void Union( int x,int y);
6 int Find( int x);
7
8 int n,m;
9 int bcj[30005];
10
11 int main()
12 {
13 int i;
14 int n1;
15 int x,y;
16 int ans = 0;
17 scanf("%d %d",&n,&m);
18 for( i=1; i<=n; i++) bcj[i] = -1; //初始化并查集
19
20 while( m-- )
21 {
22 scanf("%d",&n1);
23 for( i=1; i<=n1; i++)
24 {
25 if( i==1 )
26 {
27 scanf("%d",&x);
28 }
29 else
30 {
31 scanf("%d",&y);
32 Union(x,y);
33 }
34 }
35 }
36 for( i=1; i<=n; i++)
37 {
38 if( bcj[i]<ans ) ans = bcj[i]; //负数需寻找最小的值
39 }
40 ans = 0-ans; //用负数表示集合中元素的个数
41 printf("%d",ans);
42 return 0;
43 }
44
45 //以下是并查集的两个基本操作
46 int Find( int x)
47 {
48 if(bcj[x]<0) return x;
49 return bcj[x] = Find(bcj[x]);
50 }
51
52 void Union( int x, int y)
53 {
54 x = Find(x);
55 y = Find(y);
56
57 if( x==y ) return;
58 bcj[x] += bcj[y];
59 bcj[y] = x;
60 }
并查集的应用
...查询问题。常常在使用中以森林来表示。应用 若某个朋友圈过于庞大，要判断两个人是否是在一个朋友圈，确实还很不容易，给出某个朋友关系图，求任意给出的两个人是否在一个朋友圈。规定：x和y是朋友，y和z是朋友，... 查看详情
并查集的应用
...查询问题。常常在使用中以森林来表示。应用 若某个朋友圈过于庞大，要判断两个人是否是在一个朋友圈，确实还很不容易，给出某个朋友关系图，求任意给出的两个人是否在一个朋友圈。规定：x和y是朋友，y和z是朋友，... 查看详情
简单并查集归纳
...一边查找一边并集的数据结构，简单的并查集经常应用于朋友圈等题目，即：x和y是朋友，y和z是朋友，则x和z是朋友，下面给出一组数据表示xx和yy是朋友，最后问一共有多少个朋友圈。这类问题一般用并查集解决比较快。下面... 查看详情
求解朋友关系中的朋友圈数量
问题描述：给出10w条人和人之间的朋友关系，求出这些朋友关系中有多少个朋友圈样例A-B、B-C、D-E、E-F，这四对关系中存在2个朋友圈解题思路：并查集，而题目只需要求出朋友圈数量，并不需要求出各朋友圈，所以该并查集的... 查看详情
7-25朋友圈(代码片段)
7-25朋友圈（25分）某学校有N个学生，形成M个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好，形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据“我的朋友的朋友也是我的朋友”这个推论可以得出，如... 查看详情
并查集朋友圈问题
朋友的朋友是朋友，敌人的敌人是朋友 #include<iostream>#include<iomanip>usingnamespacestd;intr[1001][1001]={0};classUnionSet{public: UnionSet(intsize):n(size),set(newint[size]) { for(inti=0;i<size;i 查看详情
朋友(并查集的删除操作可看作是插入操作的逆序)
...村长，现在小z调查他们村上的关系。如果村民a和村民b是朋友，村民b和村民c是朋友，那么村民a和村民c也是朋友。那么村上的村民就会形成一个“朋友”团队，现在小z想知道他们村长有多少个这样的团队。同时，他们村会有人... 查看详情
数据结构一篇文章学懂并查集+lrucache，拿来吧你！(代码片段)
...集的结构解释并查集的实现并查集相关习题习题1.leetcode朋友圈习题2.leetcode等式方程的可满足性并查集的思考与提升二、LRUCache的介绍1.什么是LRUCache习题.LRU缓存机制总结好文建议收藏！！并查集的概念并查集作为一种数... 查看详情
[小米]并查集
...的好友（好友的好友的好友…）。则觉得他们属于同一个朋友圈，请敲代码求出这n个人里一共同拥有多少个朋友圈。假如：n=5。m=3，r={{1,2},{2,3},{4,5}}，表示有5个人。1和2是好友，2和3是好友，4和5是好友。则1、2、3属于一个朋友... 查看详情
并查集的一般操作③
...出现了一群强盗。如果两个强盗遇上了，那么他们要么是朋友，要么是敌人。而且有一点是肯定的，就是： 我朋友的朋友是我的朋友； 我敌人的敌人也是我的朋友。 两个强盗是同一团伙的条件是当且仅当他们是朋友... 查看详情
并查集的优化及应用
2018-05-0115:13:08并查集是一个时空复杂度非常优越的数据结构，并且通过优化后其复杂度为<O(1)，O(n)>。并查集的优化主要有两个方面：路径压缩按rank来合并路径压缩：按rank合并：publicclassUnionFindSetprivateint[]parent;privateint[]rank;p... 查看详情
今天做题做到了并查集相关的内容~简单介绍一下关于并查集的东西
就例如一个非常简单的题~有一堆人其中某些人是朋友有如下的规则如果A和B是朋友B和C是朋友那么A和C也是朋友~最后我们有n次的查询每次查询问其中两个人是不是朋友？这个题我们就可以用到集合的思想~例如A和B是朋友我们可以... 查看详情
poj2236（并查集的应用）(代码片段)
WirelessNetworkTimeLimit: 10000MS MemoryLimit: 65536KTotalSubmissions: 35832 Accepted: 14863DescriptionAnearthquaketakesplaceinSoutheastAsia.TheACM(AsiaCooperatedMedicalt 查看详情
pat1013battleovercities（25分）(并查集)(代码片段)
1013 BattleOverCities（25 分）Itisvitallyimportanttohaveallthecitiesconnectedbyhighwaysinawar.Ifacityisoccupiedbytheenemy,allthehighwaysfrom/towardthatcityareclosed.Wemustknowimmediatelyifwenee 查看详情
❤️数据结构入门❤️（2-5）-并查集
文章目录一、并查集的定义二、并查集的图解三、并查集的实现1、并查集的插入2、并查集的删除3、并查集的修改4、并查集的查找四、并查集的刷题实战一、并查集的定义二、并查集的图解三、并查集的实现1、并查集的插入2、... 查看详情
并查集的一般操作②
RT 题目描述 明天就是母亲节了，电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢？听说在某个网站上有卖云朵的，小朋友们决定一同前往去看看这种神奇的商品，这个店里有n朵云，云... 查看详情
并查集的基础
...ss/article/details/7724401/史上最容易理解的解答！没有之一。并查集能实现的功能：判断是否成环，计算共有多少个非连通图。。。待日后填坑在最小生成树中应用并查集最简代码！intf(intx){returnx==pre[x]?x:pre[x]=f(pre[x]);} voidmix(inta,... 查看详情
并查集的简介
最近做题用到了并查集索性就把自己所掌握的相关知识总结一下。 并查集(union-findsets),CLRS上称为disjoint-set,是一组不相交的动态集合S1,S2,....Sk。它能够实现较快的合并和判断元素所在集合的操作，应用比较广泛，如其求... 查看详情