并查集

基础知识:如果数据不是实时变化,本类问题可以用 BFS 或者 DFS 的方式遍历,如果数据实时变化 (data stream) 则并查集每次的时间复杂度可以视为 O (1);需要牢记合并与查找两个操作的模板

常见题目:

  • Leetcode 721 Accounts Merge
  • Leetcode 547 Number of Provinces
  • Leetcode 737 Sentence Similarity II
  • Leetcode 305 Number of Islands II
最后更新: 2/27/2024, 6:53:03 AM