面试保安的题，把程序员整不会了

主要观点总结

本文描述了一个关于园区建筑群的筛选问题。通过并查集算法，根据建筑间的道路距离来判断是否属于同一个建筑群。输入包括建筑数量、道路数量和最小距离限制。目标是确定园区中的建筑群数量。

关键观点总结

关键观点1: 问题概述

描述了一个园区内的建筑群筛选问题，需要根据建筑间的道路距离来判断是否属于同一个建筑群。

关键观点2: 算法选择

采用并查集算法来解决该问题，这是一种高效的数据结构，用于快速合并集合和查找元素所属的集合。

关键观点3: 算法流程

1. 初始化并查集，每个建筑的父节点初始化为自身。2. 读取输入的建筑数量、道路数量和最小距离限制。3. 读取每条道路的信息，根据步数是否小于等于K来合并建筑。4. 统计并查集中不同祖先的数量，即为建筑群的数量。

关键观点4: 时空复杂度

时间复杂度为O(n)，空间复杂度为O(n)。

关键观点5: 代码实现

提供了Python、C++和Java三个版本的代码实现。

正文

请到「今天看啥」查看全文

第一行有三个整数 N 、 M 、 K ，分别表示建筑的数量、路的数量以及两个建筑群之间最近两个建筑的最小距离 K 。其中：

2≤ N ≤100

1≤ M ≤2 N ×( N −1)

1≤ K ≤100000

接下来有 M 行，每行包含三个整数 a 、 b 、 d ，表示建筑 a 和建筑 b 之间的步数为 d 。其中：

1≤ a , b ≤ N

1≤ d ≤100000

输出格式

输出一个整数，表示园区里建筑群的数量。

样例

输入样例 1

6 5 3
1 2 1
1 3 4
2 4 2
3 5 3
3 6 2

输出样例 1

2

提示 1

根据输入数据，建筑群被划分为两个部分：[1,2,4] 和 [3,5,6]，因为这两个建筑群之间最近的两个建筑之间的步数大于 3。

输入样例 2

5 5 4
1 2 1
1 3 4
2 4 2
3 5 2
4 5 5

输出样例 2

请到「今天看啥」查看全文