策划：组队才有加成！图论：单节点也是完全图
作为某氪金手游的掉落算法工程师，你的日常就是在概率和期望之间走钢丝，确保氪佬满意、白嫖党不至于删游、策划的 KPI 刚刚好。今天一大早，策划就带着一脸"我有好主意"的表情晃到你工位前。
“我们要搞个’固定队额外掉落加成系统！同一个队的人，如果彼此都配合过，就给他们额外的橙色装备掉率！”策划激情澎湃地比划，“这样玩家就会自发社交，我们的日活数据就好看了！”
你觉得这逻辑有点离谱——什么叫’彼此都配合过’？策划挠了挠头：“嗯…就是队里每两个人都至少组过一次队，而且队伍是封闭的，不能有外人掺和。比如你和 A 打过，A 和 B 打过，那你和 B 也必须打过。懂了没？”
你差点一口老血喷在键盘上。这不就是让你在玩家组队记录构成的无向图里，找出所有完全连通分量吗？！换句话说，就是一群既“全连接”又“绝对自闭”的玩家小圈子。你试图解释：“所以你想统计的就是图中的完全连通——”
但策划显然没耐心听你科普：“完全什么？不用给我整术语，反正你把数字给我就行，下周公会战活动要用。”
你叹了口气，想把策划丢进副本当BOSS刷。但KPI在手，你只能硬着头皮打开玩家组队记录的数据库：
n个玩家，编号0到n-1edges里是一条条组队记录——表示两个玩家曾经一起下过本
你的任务，就是在这张图里找出所有"完美固定队"的数量。
完美固定队的鉴定公式
首先明确问题本质：玩家们形成一个个封闭的小圈子——连通分量；圈子里任意两人都组过队——这个分量是一张完全图。你要找的，就是图中既是连通分量又是完全图的子图——完全连通分量。
好在大脑深处的图论存档还没完全坏道。关于完全图，大学老师那句刻进 DNA 的话自动弹了出来：
“一个有 k 个节点的完全图，恰好有 k × (k - 1) / 2 条边。”
道理也很简单，就是个等差数列求和。在一个 k 人完美固定队里，第一个人要和其余 k-1 人组队，第二个人再和剩下的 k-2 人组队（和第一个已经算过了），依此类推，最后一对是倒数第二人和最后一人。总组队次数就是：
(k-1) + (k-2) + (k-3) + … + 2 + 1 = k × (k - 1) / 2
如果少一条边，说明队伍里有两人从来没有配合过——这是策划口中的“塑料固定队”，不配拿加成。鉴定标准无比清晰：一个连通分量要成为完美连通分量，它的成员数 k 和内部边数必须满足 实际边数 = k × (k - 1) / 2。
理论就位，接下来要考虑的只有一件事——怎么在图上又快又稳地揪出所有小团体，然后验一验它们内部的边数有没有达标。
并查集：先把队伍圈出来
你习惯性地掏出祖传的并查集——这玩意儿专治各种连通性问题。先把所有一起打过本的玩家合并成一个个“潜在固定队”，然后再逐个验身——看每个队伍内部的边数是否满足完全图公式。
并查集的合并逻辑很朴素：遍历 edges，把每条边的两个节点 union 到一起。为了给策划留点面子，你还在合并时加了按秩合并——让老队伍当队长（秩高的当根节点），避免队伍层级太深，传话传半天（find操作变慢）。路径压缩顺手加上，下次查找队长时直接 O(1)。
parent = list(range(n)) # 初始化：每个人都是自己的队长
rank = [0] * n # 队伍等级：新队伍都是1级
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # 路径压缩
x = parent[x]
return x
def union(x, y):
px, py = find(x), find(y)
if px == py:
return
# 按秩合并：等级高的当队长
if rank[px] < rank[py]:
px, py = py, px
parent[py] = px # 小队伍并入大队伍
if rank[px] == rank[py]:
rank[px] += 1 # 平级时，被挂靠的队长升一级
for u, v in edges:
union(u, v)
队伍分好了，接下来就是简单的统计了：
数人头：每个队伍有多少玩家 数配合次数：每个队伍打过多少次配合（边数）
你写了两个循环，分别输出每个队伍内部的玩家数和边数，再用个循环，把每个队伍和理论值 k * (k - 1) / 2 比对，如果一个队伍有 k 个人，内部边数恰好等于 k × (k - 1) / 2，那它就是完美固定队，计数加一。
# 统计每个队伍的玩家数
block_nodes = {}
for i in range(n):
root = find(i)
block_nodes[root] = block_nodes.get(root, 0) + 1
# 统计每个队伍的边数
block_edges = {}
for u, v in edges:
root = find(u)
block_edges[root] = block_edges.get(root, 0) + 1
# 数学鉴定
ans = 0
for root in block_nodes:
v = block_nodes[root] # 队伍人数
e = block_edges.get(root, 0) # 实际配合次数
if e == v * (v - 1) // 2:
ans += 1
return ans
虽然今天的数据范围不算大，但“先合并再逐个检查组内边数”这套流程总让你觉得多跑了一趟——合并完之后要回头遍历所有边来统计内部边数，等于把图扫了两遍。
明明在合并的时候就能顺便统计的东西，为什么要分两趟？你决定换一种更利落的姿势。
DFS：一脚踩到底，顺手记总账
思路非常直球：从每个没被访问过的节点出发，用 DFS 把整个连通分量一次性趟完。跑的过程中，你手里捏着两个计数器：V 记录这个小团体里有多少活人，E 记录所有人通讯录里的好友总数（图论术语叫“度数之和”，但你更愿意叫它“社交牛逼指数总和”）。
一个 V 人的完美固定队，内部应该有 V×(V-1)/2 条边。但 DFS 在统计的时候，每踩到一个节点就把它的全部好友数往 E 里加——每条边两端的人都会记一次，所以 E 里攒下的是边数的两倍。换句话说，对于真正的自闭全连接小队，E 应该恰好等于 V×(V-1)。
这个判定妙就妙在它同时验了两件事：如果 E < V×(V-1)，说明队内边数不够，有人互不认识，是塑料固定队；如果 E > V×(V-1)，说明有人偷偷和队外的人组队，社交海王实锤，团队不“自闭”。只有不多不少刚刚好，才算完美。
def countCompleteComponents(n: int, edges: List[List[int]]) -> int:
g = [[] for _ in range(n)]
for u, v in edges:
g[u].append(v)
g[v].append(u)
visited = [False] * n
def dfs(u):
nonlocal V, E
V += 1
E += len(g[u])
visited[u] = True
for v in g[u]:
if not visited[v]:
dfs(v)
ans = 0
for i in range(n):
if not visited[i]:
V = E = 0
dfs(i)
if E == V * (V - 1):
ans += 1
return ans
一个 visited 数组管住所有节点，每次发车就新建一个栈，把起点塞进去，然后开始深挖。没有回头路，没有二次统计，搜完一块就扔一块，栈弹出最后一个节点时结论已经落地。时间复杂度 O(n+m)，空间 O(n+m)，比并查集少了一轮“遍历所有边归类”的扫尾工作。
尾声
你把全服完美固定队的数量打包发给策划：“统计完毕，名单见附件。这些队伍内部人人配合过，对外绝不多看，可以放心发额外掉落buff。”
策划秒回：“等等，你名单里怎么还有一堆单人队？一个人也算固定队？”
“单人成军，也算完美团队。”你淡定地解释，“毕竟一个人不需要配合任何人，从逻辑上来说确实是‘全连接’的——没有内部缺失的边，也没有外部社交，完美满足所有条件。”
策划沉默了好几秒：“……那白嫖党一个人刷本也能享受额外加成？”
你端起冰美式，敲下回复：“数学上是的。你设计的是社交激励系统，但图论不管这些——单点，也是一种完美 。”
本作品采用
知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议
进行许可。