目录
题目
思路
Code
题目
题目内容：
某公司机房部署了编号为 0 至 n-1 的 n 台路由器。网络工程师通过网桥将路由器两两连接，网络连通具有传递性：若 A 与 B 连通、B 与 C 连通，则 A 与 C 也连通。
给定全部连接关系和一台目标路由器，求与目标路由器连通的其他路由器数量，不包含目标路由器自身。
1 ≤ n ≤ 10000。每条连接 [u,v] 满足 0 ≤ u,v ≤ n-1，target 满足 0 ≤ target ≤ n-1。
输入描述：
第一行输入路由器数量 n。
第二行输入 JSON 风格的二维连接数组 links。
第三行输入目标路由器编号 target。
输出描述：
输出一个整数，表示与 target 连通且不包含 target 自身的路由器数量。
样例 1
输入：
6 [[0,1],[1,2],[3,4],[4,5]] 0输出：
2说明：
0 与 1 连通，1 与 2 连通，因此与 0 连通的其他路由器为 1 和 2。
样例 2
输入：
7 [[0,3],[3,5],[5,0],[2,6],[1,3]] 5输出：
3样例 3
输入：
4 [] 2输出：
0思路
整体思路：使用并查集把每条无向连接的两个端点合并，并在每个连通分量的根节点记录分量大小。
第一步：初始化每台路由器的父节点为自身，分量大小为 1。
第二步：遍历 links。对一条连接的两个端点分别寻找根节点；若根不同，就把较小分量合并到较大分量，并累加分量大小。
第三步：查找 target 最终所属的根节点。该根记录的分量大小包含 target，所以答案需要减 1。
正确性说明：并查集合并一条边后，边两端及它们原有分量中的所有节点属于同一集合；处理全部边后，同集合当且仅当图中存在连通路径，因此根节点大小准确表示连通分量大小。
边界处理：空连接数组返回 0；自环、重复边和环不会重复增加分量大小；孤立目标路由器所在分量大小为 1。
复杂度分析：设连接数为 e，路径压缩和按大小合并后的时间复杂度为 O((n+e)α(n))，空间复杂度为 O(n)。
Code
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.regex.Matcher; import java.util.regex.Pattern; public class Main { static int[] parent; static int[] sizes; static int find(int node) { // 递归返回时把节点直接连接到根，压缩重复查询路径。 if (parent[node] != node) { parent[node] = find(parent[node]); } return parent[node]; } static void union(int a, int b) { int rootA = find(a); int rootB = find(b); if (rootA == rootB) { return; } // 按分量大小合并，保证较小树挂到较大树下。 if (sizes[rootA] < sizes[rootB]) { int temporary = rootA; rootA = rootB; rootB = temporary; } parent[rootB] = rootA; sizes[rootA] += sizes[rootB]; } public static void main(String[] args) throws Exception { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(reader.readLine().trim()); String linksLine = reader.readLine(); int target = Integer.parseInt(reader.readLine().trim()); parent = new int[n]; sizes = new int[n]; for (int node = 0; node < n; node++) { parent[node] = node; sizes[node] = 1; } // 正则只提取 links 行中的整数，兼容空数组和 JSON 标点。 Matcher matcher = Pattern.compile("\\d+").matcher(linksLine); List values = new ArrayList<>(); while (matcher.find()) { values.add(Integer.parseInt(matcher.group())); } for (int index = 0; index < values.size(); index += 2) { union(values.get(index), values.get(index + 1)); } // 根节点记录完整分量大小，按题意扣除 target 自身。 // 输入解析把连接数组中的 JSON 标点去掉，只保留按出现顺序成对的路由器端点。 // 合并循环处理每条无向连接；只有两个根不同的分支才更新父节点与分量大小，避免重复计数。 // 最终答案读取目标节点根上的分量状态并减去自身，输出一个非负整数。 System.out.println(sizes[find(target)] - 1); } }Go
package main import ( "bufio" "fmt" "os" "regexp" "strconv" ) func find(parent []int, node int) int { // 路径压缩把查询路径上的节点直接连接到当前分量根。 if parent[node] != node { parent[node] = find(parent, parent[node]) } return parent[node] } func main() { reader := bufio.NewReader(os.Stdin) var n int fmt.Fscanln(reader, &n) links, _ := reader.ReadString('\n') var target int fmt.Fscan(reader, &target) parent := make([]int, n) sizes := make([]int, n) for node := 0; node < n; node++ { parent[node] = node sizes[node] = 1 } // JSON 标点不参与计算，正则依次提取每条边的两个端点。 matches := regexp.MustCompile(`\d+`).FindAllString(links, -1) for index := 0; index < len(matches); index += 2 { a, _ := strconv.Atoi(matches[index]) b, _ := strconv.Atoi(matches[index+1]) rootA := find(parent, a) rootB := find(parent, b) if rootA == rootB { continue } // 小分量挂到大分量后，仅新根的 sizes 保持有效。 if sizes[rootA] < sizes[rootB] { rootA, rootB = rootB, rootA } parent[rootB] = rootA sizes[rootA] += sizes[rootB] } // 分量大小含 target，本题只统计其余路由器。 // 输入解析把连接数组中的 JSON 标点去掉，只保留按出现顺序成对的路由器端点。 // 合并循环处理每条无向连接；只有两个根不同的分支才更新父节点与分量大小，避免重复计数。 // 最终答案读取目标节点根上的分量状态并减去自身，输出一个非负整数。 fmt.Println(sizes[find(parent, target)] - 1) }C
#include #include #include #define MAX_LINK_LINE 2000000 int find_root(int parent[], int node) { // 递归回写根节点，使同一连通分量的后续查询缩短路径。 if (parent[node] != node) { parent[node] = find_root(parent, parent[node]); } return parent[node]; } int main(void) { int n; if (scanf("%d", &n) != 1) { return 0; } int ch; while ((ch = getchar()) != '\n' && ch != EOF) { } char *links = malloc(MAX_LINK_LINE); if (links == NULL || fgets(links, MAX_LINK_LINE, stdin) == NULL) { free(links); return 0; } int target; scanf("%d", &target); int *parent = malloc((size_t)n * sizeof(int)); int *sizes = malloc((size_t)n * sizeof(int)); for (int node = 0; node < n; node++) { parent[node] = node; sizes[node] = 1; } // 扫描连接行中的数字；每相邻两个数字组成一条无向边。 int endpoints[2]; int endpoint_count = 0; char *cursor = links; while (*cursor != '\0') { if (!isdigit((unsigned char)*cursor)) { cursor++; continue; } char *end; endpoints[endpoint_count++] = (int)strtol(cursor, &end, 10); cursor = end; if (endpoint_count == 2) { int root_a = find_root(parent, endpoints[0]); int root_b = find_root(parent, endpoints[1]); if (root_a != root_b) { // 只在不同分量间合并，重复边和环不会重复增加大小。 if (sizes[root_a] < sizes[root_b]) { int temporary = root_a; root_a = root_b; root_b = temporary; } parent[root_b] = root_a; sizes[root_a] += sizes[root_b]; } endpoint_count = 0; } } // target 所在分量的大小减一，排除目标路由器本身。 // 输入解析把连接数组中的 JSON 标点去掉，只保留按出现顺序成对的路由器端点。 // 合并循环处理每条无向连接；只有两个根不同的分支才更新父节点与分量大小，避免重复计数。 // 最终答案读取目标节点根上的分量状态并减去自身，输出一个非负整数。 printf("%d\n", sizes[find_root(parent, target)] - 1); free(links); free(parent); free(sizes); return 0; }【华为od机试真题Python+JS+Java+Go合集】【超值优惠】：Py/JS/Java/Go合集
【华为od机试真题Python】：Python真题题库
【华为od机试真题JavaScript】：JavaScript真题题库
【华为od机试真题Java&Go】：Java&Go真题题库
【华为od机试真题C++】：C++真题题库
【华为od机试真题C语言】：C语言真题题库
【华为od面试手撕代码题库】：面试手撕代码题库
【华为od机试面试交流群】【文章底部有二维码链接，可扫码加交流群】
华为OD机试:二本院校有机会吗? 有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。