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