某学校有 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
题目分析: 这道题是并查集的利用 没什么需要注意的
- #define _CRT_SECURE_NO_WARNINGS
- #include<stdio.h>
- #include<string.h>
- #include<malloc.h>
- int S[30005];
- int Find(int x)
- {
- for (; S[x]> 0; x = S[x])
- ;
- return x;
- }
- void Union(int x, int y)
- {
- int X = Find(x);
- int Y = Find(y);
- if (X == Y)return;
- S[X] += S[Y];
- S[Y] = X;
- }
- int main()
- {
- int N, M;
- int x, y;
- int have = 0;
- scanf("%d%d", &N, &M);
- for (int i = 0; i <= N; i++)S[i] = -1;
- while (M--)
- {
- int num;
- scanf("%d", &num);
- for (int i = 0; i < num; i++)
- {
- if (i == 0)
- scanf("%d", &x);
- else
- {
- scanf("%d", &y);
- Union(x, y);
- }
- }
- }
- for (int i = 1; i <=N; i++)
- {
- if (S[i] < have)
- have = S[i];
- }
- have = 0 - have;
- printf("%d", have);
- }
- View Code
来源: http://www.bubuko.com/infodetail-3229477.html