P7031: 最强大的友谊小组
传统题
2.000s
时间限制
256MB
内存限制
3 提交
1 解决
【题目描述】
【题目描述】
Farmer John
有 N
头奶牛（2≤N≤10^5
），编号为 1…N
。这些奶牛中有 M
（1≤M≤2×10
^5
）对朋友。
一组奶牛被称为是「小团体」，如果该组中的每头奶牛都可以从该组中的每头其他奶牛出发通过完全位于该组内的一系列朋友关系到达（连接到组外奶牛的朋友关系无效）。小团体的「强度」是组内奶牛的最小组内朋友数乘以组内奶牛的数量（同样，注意连接到组外奶牛的朋友关系不计入此定义）。
求所有小团体的最大强度。
【
输入格式】
（从终端 /
标准输入读入）：
输入的第一行包含 N
和 M。
以下 M
行每行包含两个整数 ui 和 vi，表示奶牛 ui
和 vi 是朋友（1≤ui,vi≤N，ui≠vi
）。每个奶牛无序对至多出现一次。
【
输出格式】
（输出至终端 /
标准输出）：
输出一行，包含所有小团体的最大强度。
【
输入样例】
：
8 10
1 2
1 3
1 4
2 3
2 4
3 4
1 5
2 6
3 7
4 8
【
输出样例】
：
12
【样例说明】
可以观察到最大强度来自编号为 1,2,3,4
的奶牛组。该组内奶牛的最小朋友数为 3，故答案为 4×3=12
。
【
测试点性质】
：
对于 1≤T≤3
，测试点 TT
满足 N≤16。
对于 4≤T≤9
，测试点 TT
满足 N≤1000。
对于 10≤T≤20
，测试点 T
没有额外限制。