面试题库 › 游戏开发 › 并查集求无向图连通分量个数

并查集求无向图连通分量个数

难度 ★★☆在 2 场真实面经中被问到 方向:游戏开发考点:图论

哪些公司问过

滴滴1网易互娱1

常见岗位:Java 后端、游戏服务端

答案要点

  1. 初始化每个节点为独立集合,连通分量计数为 N
  2. 遍历每条边合并两端点,根不同时合并并让计数减一
  3. find 用路径压缩,union 用按秩或按大小合并,均摊近似常数
  4. 求最大连通分量大小时维护 size 数组,合并时累加
  5. 注意节点编号起点、孤立点、自环和重边等边界

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题