3.1 - Initialisation
3.2 - Mutual Friends
#简单理解
查看思路
在完成上述初始化以后，想要找到 mutual friends 就非常容易了。
给定 人物A，人物B
我们需要检查人物A的
关注和被关注是否同时存在人物B的keyBitVectorSet 可以查询
3.3 - AI Clusters
#有难度 FIT054
🔺注意：为了时间复杂度的降低，为代码和解题思路会在周一周二更新。不会有大的变动。
查看思路
理解题意：
📖 题目理解
- 平台 TipTop 想要检测 AI 群集 (AI Clusters)。
- AI Cluster 定义：
- 一组用户之间 全部互为好友（即形成一个完全图 / clique）。
- 该组用户 没有与外部用户的连接。
- 特殊情况：
- 没有任何朋友的用户（孤立节点）也算作一个大小为 1 的 AI cluster。
🚀 思路概要
- 遍历所有用户 → 用 BFS/队列 找到他们所在的连通分量。
- 检查连通分量是否是完全图 → 即每个用户的好友数应为 (该分量大小 - 1)。
- 检查是否无外部连接 → 所有好友必须在这个分量里。
- 保留符合条件的分量，作为一个 AI cluster。
🔎 核心步骤
1. 使用 BFS 找连通分量
- 初始化：一个全局
visited集合，记录已访问的用户。
- 遍历所有用户：
- 如果该用户未访问过 → 以此用户为起点，做 BFS。
- BFS 用队列扩展，找到所有与其相连的用户，形成一个 子集（连通分量）。
👉 得到的子集是图中的一个 connected component。
2. 判断连通分量是否是 AI cluster
对于 BFS 得到的每个连通分量：
- 完全互连条件：
- 如果子集大小 = k，
- 则子集中的每个用户的好友数必须是 (k - 1)。
- 无外部连接条件：
- 取每个用户的好友列表，必须全部包含在该子集里。
只有满足这两个条件，这个子集才是 AI cluster。
3. 特殊情况处理
- 如果用户完全没有好友：
- BFS 得到的子集大小 = 1。
- 按定义，这也是一个 cluster。
🛠️ 数据结构选择
- 队列 (queue) → BFS 遍历
- 集合 (set / BitVectorSet) → 存储已访问节点
- 集合 (ArraySet/BitVectorSet) → 存储每个 cluster
作业要求说明：内部结构不限，可以是数组的数组、链表的链表等，不影响分数。
📊 示例解析
示例 1
用户:
[A, B, C, G, H, K]- A ↔ B, B ↔ C, A ↔ C
- G ↔ H
- K 无好友
结果:
示例 2
用户:
[A, B, C, D, E]- A ↔ B
- C ↔ E (但不是互为好友，因为 E 没有指向 C) → 不算 cluster
- D 孤立
结果:
⚡ 时间复杂度分析（非评分点，仅理解）
- BFS：每个用户最多被访问一次 → O(n + m)，n=用户数，m=边数
- 检查完全图：每个连通分量 O(k²)，但一般较小
- 总体上可接受，题目说明只要能在大输入下快速完成即可。
✅ 最终总结
- 用 BFS 找到连通分量
- 判断是否为完全图（所有人互为好友）
- 判断无外部连接
- 孤立用户也算 AI cluster
- 输出所有符合条件的子集
大致思路
- BFS 分组：
- 用位掩码 + 队列做广度优先搜索，找到每一个 连通分量，存进
AI_clusters。
- 去重：
- 如果两个集合有交集（共享节点），则丢弃。
- 筛选“完整团”：
- 检查每个集合是否是一个 完全图（clique）：
- 即集合内每个节点都应该连接到集合里其他所有节点。
- 如果不是，就移除该集合。
难点在于降低时间复杂度。