[USACO22DEC] Strongest Friendship Group G

Luogu

IDLGP8905

Time2000ms

Memory256MB

DifficultyP5

USACO并查集2022枚举连通块

Farmer John 有 $N$ 头奶牛（$2 \le N \le 10^5$），编号为 $1\cdots N$。这些奶牛中有 $M(1 \le M \le 2\times 10^5)$ 对朋友。一组奶牛被称为是「小团体」，如果该组中的每头奶牛都可以从该组中的每头其他奶牛出发通过完全位于该组内的一系列朋友关系到达（连接到组外奶牛的朋友关系无效）。小团体的「强度」是组内奶牛的最小组内朋友数乘以组内奶牛的数量（同样，注意连接到组外奶牛的朋友关系不计入此定义）。求所有小团体的最大强度。 ## Input 输入的第一行包含 $N$ 和 $M$。以下 $M$ 行每行包含两个整数 $u_i$ 和 $v_i$，表示奶牛 $u_i$ 和 $v_i$ 是朋友（$1 \le u_i,v_i \le N,u_i\neq v_i$）。每个奶牛无序对至多出现一次。 ## Output 输出一行，包含所有小团体的最大强度。 [samples] ## Note ### 样例 1 解释可以观察到最大强度来自编号为 $1,2,3,4$ 的奶牛组。该组内奶牛的最小朋友数为 $3$，故答案为 $4 \times 3=12$。 ### 测试点性质 - 对于 $1 \le T \le 3$，测试点 $T$ 满足 $N \le 16$。 - 对于 $4 \le T \le 9$，测试点 $T$ 满足 $N \le 1000$。 - 对于 $10 \le T \le 20$，测试点 $T$ 没有额外限制。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[USACO22DEC] Strongest Friendship Group G",
    "description": {
      "content": "Farmer John 有 $N$ 头奶牛（$2 \\le N \\le 10^5$），编号为 $1\\cdots N$。这些奶牛中有 $M(1 \\le M \\le 2\\times 10^5)$ 对朋友。 一组奶牛被称为是「小团体」，如果该组中的每头奶牛都可以从该组中的每头其他奶牛出发通过完全位于该组内的一系列朋友关系到达（连接到组外奶牛的朋友关系无效）。小团体的「强度」是组内奶牛的最小组内朋友数乘以",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8905"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Farmer John 有 $N$ 头奶牛（$2 \\le N \\le 10^5$），编号为 $1\\cdots N$。这些奶牛中有 $M(1 \\le M \\le 2\\times 10^5)$ 对朋友。\n\n一组奶牛被称为是「小团体」，如果该组中的每头奶牛都可以从该组中的每头其他奶牛出发通过完全位于该组内的一系列朋友关系到达（连接到组外奶牛的朋友关系无效）。小团体的「强度」是组内奶牛的最小组内朋友数乘以...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments