题目核心思路

问题转化

我们需要在无向图中找到一个四元组 $(a,b,c,d)$，使得这$4$个点构成的$6$条边中恰好有$5$条边存在，即形成一个**$K_4$减去一条边**的结构。

关键观察

目标结构等价于：存在一条边$(x,y)$和它们的两个公共邻居$u,v$，满足$u$和$v$之间没有边。

形式化描述：

• 选择一条边$(x,y) \in E$
• 找到两个不同的点$u,v \in N(x) \cap N(y)$（公共邻居）
• 满足$(u,v) \notin E$

算法框架

1. 按度数分治：将点分为大度数点（度数$> \sqrt{m}$）和小度数点
2. 预处理大度数点：对每个大度数点，用bitset存储其邻居集合
3. 枚举边$(x,y)$：对于每条边，高效计算公共邻居集合$N(x) \cap N(y)$
   • 若$x,y$都是大度数点：用bitset的按位与操作，复杂度$O(\frac{n}{w})$
   • 若一个是小度数点：枚举小度数点的邻居检查
   • 若都是小度数点：直接双循环枚举
4. 在公共邻居中找非邻接对：在公共邻居集合中寻找一对$u,v$满足$(u,v) \notin E$

复杂度分析

• 大度数点最多$O(\sqrt{m})$个
• bitset操作复杂度$O(\frac{n}{w})$
• 总复杂度$O(m \sqrt{m} + \frac{nm}{w})$，在$n,m \leq 10^5$时可接受

该算法利用度数分块和bitset优化，高效解决了在大型图中寻找特定子图结构的问题。