题目内容

某公司基地园区很大，里面有$N$个建筑，依次编号为$1$到$N$，通过$M$条路将这些建筑连接在一起，这$N$个建筑根据之间的距离，被分为不同的建筑群。云小核喜欢饭后散步，并用步数计算了每条路的长度。经过一段时间的散步，云小核发现了一个规律，两个建筑群间最近的两个建筑之间，步数大于$K$步。两个建筑群之间，可能没有路。云小核把每条路的步数给了你，请你计算园区里有多少个建筑群?

输入描述

第一行有三个整数$N、M、K$，分别表示$N$个建筑，$M$条路，两个建筑群间最近两个建筑之间的最小距离$K$，$2 <= N <= 100$， $1 <= M <= N*(N-1)/2$,$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

输出

2 

说明

样例2

输入

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

输出

1

说明

样例3

输入

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

输出

2

说明

题解

问题描述

给定建筑数 N，道路数 M，距离阈值 K，以及每条道路的连接信息，计算园区内有多少个独立的建筑群。

思路

为了确定建筑群的数量，我们需要根据给定的步数阈值 K 将建筑划分为不同的群组。具体步骤如下：

1. 过滤道路：首先，只考虑那些步数长度 d 小于或等于 K 的道路。因为这些道路上的步数不超过阈值 K，可以将通过这些道路相连的建筑视为同一个群组的一部分。

2. 构建连接关系：使用 并查集（Union-Find） 数据结构来管理建筑之间的连接关系。对于每一条符合条件的道路，将连接的两个建筑合并到同一个群组中。

3. 计算群组数量：遍历所有建筑，找出其最终的根节点（代表群组的唯一标识），并统计不同根节点的数量，即为建筑群的总数。

步骤

1. 初始化并查集：为每个建筑初始化其父节点为自身。

2. 处理道路信息：

   • 遍历所有道路。
   • 对于每条道路，如果步数 d ≤ K，则将连接的两个建筑合并到同一个群组中。

3. 统计群组数量：

   • 遍历所有建筑，找到每个建筑的根节点。
   • 使用集合（Set）来存储所有不同的根节点。
   • 最终集合的大小即为建筑群的数量。

完整代码

python

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n + 1)]  # 初始化每个节点的父节点为自己
        self.rank = [0] * (n + 1)  # 用于优化的秩

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:  # 合并两个集合
            if self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            elif self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            else:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1

def count_building_groups(n, m, k, roads):
    uf = UnionFind(n)  # 初始化并查集

    for a, b, d in roads:
        if d <= k:  # 只考虑步数小于等于 K 的道路
            uf.union(a, b)

    # 统计建筑群数量，找出所有独立的根节点
    unique_roots = set()
    for i in range(1, n + 1):
        unique_roots.add(uf.find(i))

    return len(unique_roots)

# 输入处理
n, m, k = map(int, input().split())
roads = []
for _ in range(m):
    a, b, d = map(int, input().split())
    roads.append((a, b, d))

# 输出结果
print(count_building_groups(n, m, k, roads))

java

import java.util.*;
import java.io.*;

public class Main {
    // 并查集类
    static class UnionFind {
        private int[] parent; // 父节点数组
        private int[] rank;   // 秩数组，用于优化

        // 构造函数，初始化父节点和秩
        public UnionFind(int n) {
            parent = new int[n + 1];
            rank = new int[n + 1];
            for(int i = 0; i <= n; i++) {
                parent[i] = i; // 初始化每个节点的父节点为自己
                rank[i] = 0;   // 初始化秩为0
            }
        }

        // 查找函数，带路径压缩
        public int find(int x) {
            if(parent[x] != x) {
                parent[x] = find(parent[x]); // 路径压缩
            }
            return parent[x];
        }

        // 合并两个集合，按秩合并
        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if(rootX != rootY) { // 如果根节点不同，进行合并
                if(rank[rootX] > rank[rootY]) {
                    parent[rootY] = rootX;
                }
                else if(rank[rootX] < rank[rootY]) {
                    parent[rootX] = rootY;
                }
                else {
                    parent[rootY] = rootX;
                    rank[rootX] += 1;
                }
            }
        }
    }

    // 计算建筑群数量的函数
    public static int countBuildingGroups(int n, int m, int k, List<int[]> roads) {
        UnionFind uf = new UnionFind(n); // 初始化并查集

        for(int[] road : roads) {
            int a = road[0];
            int b = road[1];
            int d = road[2];
            if(d <= k) { // 只考虑步数小于等于 K 的道路
                uf.union(a, b);
            }
        }

        // 使用 HashSet 来统计不同的根节点
        Set<Integer> uniqueRoots = new HashSet<>();
        for(int i = 1; i <= n; i++) {
            uniqueRoots.add(uf.find(i));
        }

        return uniqueRoots.size();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取第一行输入
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();

        List<int[]> roads = new ArrayList<>();
        for(int i = 0; i < m; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int d = scanner.nextInt();
            roads.add(new int[]{a, b, d});
        }

        // 计算并输出结果
        int result = countBuildingGroups(n, m, k, roads);
        System.out.println(result);

        scanner.close();
    }
}

c++

#include <bits/stdc++.h>
using namespace std;

// 并查集类
class UnionFind {
private:
    vector<int> parent; // 父节点数组
    vector<int> rank;   // 秩数组，用于优化

public:
    // 构造函数，初始化父节点和秩
    UnionFind(int n) {
        parent.resize(n + 1);
        rank.resize(n + 1, 0);
        for(int i = 0; i <= n; i++) {
            parent[i] = i; // 初始化每个节点的父节点为自己
        }
    }

    // 查找函数，带路径压缩
    int find_set(int x) {
        if(parent[x] != x) {
            parent[x] = find_set(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    // 合并两个集合，按秩合并
    void union_set(int x, int y) {
        int rootX = find_set(x);
        int rootY = find_set(y);
        if(rootX != rootY) { // 如果根节点不同，进行合并
            if(rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            }
            else if(rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            }
            else {
                parent[rootY] = rootX;
                rank[rootX] += 1;
            }
        }
    }
};

// 计算建筑群数量的函数
int countBuildingGroups(int n, int m, int k, vector<tuple<int, int, int>> roads) {
    UnionFind uf(n); // 初始化并查集

    for(auto &road : roads) {
        int a, b, d;
        tie(a, b, d) = road;
        if(d <= k) { // 只考虑步数小于等于 K 的道路
            uf.union_set(a, b);
        }
    }

    // 使用 set 来统计不同的根节点
    set<int> uniqueRoots;
    for(int i = 1; i <= n; i++) {
        uniqueRoots.insert(uf.find_set(i));
    }

    return uniqueRoots.size();
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<tuple<int, int, int>> roads;
    for(int i = 0; i < m; i++) {
        int a, b, d;
        cin >> a >> b >> d;
        roads.emplace_back(make_tuple(a, b, d));
    }
    // 计算并输出结果
    int result = countBuildingGroups(n, m, k, roads);
    cout << result;
    return 0;
}