题目解析

问题分析

我们需要将 $n$ 个人分成两个集合：

后勤组 $S$：要求构成一个团，即集合中任意两人都互相认识。

同谋组 $T$：要求构成一个独立集，即集合中任意两人都不互相认识。

且两个集合都非空。

关键观察

图论模型：将每个人看作图中的一个顶点，认识关系看作无向边，则原图构成一个无向简单图。

后勤组 $S$ 对应原图的一个团（clique）

同谋组 $T$ 对应原图的一个独立集（independent set）

互补性：在补图中：

后勤组 $S$ 变为独立集

同谋组 $T$ 变为团

约束条件：划分必须满足：

$S \cap T = \emptyset$

$S \cup T = V$（所有顶点）

$|S| \geq 1$，$|T| \geq 1$

算法思路

特殊情况

整个图是团：任意两人都认识

同谋组最多只能有 $1$ 个人（因为两人以上就会互相认识）

方案数：选择哪一个人作为同谋组，其余作为后勤组，共 $n$ 种方案

整个图是独立集：任意两人都不认识

后勤组最多只能有 $1$ 个人（因为两人以上就会不互相认识）

方案数：选择哪一个人作为后勤组，其余作为同谋组，共 $n$ 种方案

一般情况 对于既不是团也不是独立集的一般图，需要更复杂的分析：

度数排序：将顶点按度数降序排序

枚举划分：尝试将前 $k$ 个度数大的顶点作为后勤组 $S$，后 $n-k$ 个顶点作为同谋组 $T$

验证条件：

检查 $S$ 是否构成团：$S$ 中任意两顶点间都有边

检查 $T$ 是否构成独立集：$T$ 中任意两顶点间都没有边

处理度数相同：当多个顶点度数相同时，需要考虑不同的排列顺序，每种顺序可能对应不同的有效划分

复杂度分析 朴素验证：对每个 $k$ 验证需要 $O(n^2)$，总复杂度 $O(n^3)$，对于 $n \leq 5000$ 不可行

优化方法：通过预处理邻接矩阵（$O(n^2)$ 空间）和巧妙验证，可以将复杂度降至 $O(n^2)$ 或 $O(n^2 \log n)$

实现细节

邻接矩阵：使用 $n \times n$ 的布尔矩阵存储认识关系

度数数组：记录每个顶点的度数

排序处理：对度数相同的顶点需要特别处理，考虑所有可能的相对顺序

总结

本题的核心在于识别图的特殊结构（团与独立集的划分），并通过巧妙的枚举和验证来计数有效划分方案。需要特别注意处理边界情况和度数相同顶点的排列问题。