第22课：综合实战：社交网络好友圈
进度 0/24
👥
综合实战：社交网络好友圈
好友的好友也是朋友，圈子一数便知！
📖知识引入
🤝关系建模
每个人是点，好友关系是无向边，加边就合并
🧩好友圈=连通块
直接或间接相连的人属于同一个圈，并查集来分圈
🔢数圈方法
fa[i]==i的节点个数，就是好友圈的个数
💬进阶追问
最大的圈有多少人？给每个根挂一个cnt计数器
💡
好友关系是双向的，加一条边合并一次就够，别重复合并同一个圈
🔍好友圈人数统计
#include <iostream>
using namespace std;
int fa[100005], cnt[100005]; // cnt 记录每个圈子的人数
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void unite(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return; // 已经同圈，别重复合并
fa[rx] = ry;
cnt[ry] += cnt[rx]; // 人数累加到新根上
}
// 查询 x 所在圈子的人数：cnt[find(x)]
// 初始化：fa[i]=i 且 cnt[i]=1合并时把人数累加到新根上，cnt[find(x)]随时查询。
🎯小测验
第1题：好友圈问题的本质是什么？
第2题：统计好友圈个数要数什么？
第3题：查询某人所在圈子的人数应该？
📝本课知识点
- ✓好友圈=连通块
- ✓根的个数=圈子数
- ✓cnt数组记圈子人数
第22课完成！继续探索下一课吧 🚀