目录题目思路Code题目题目内容某公司机房部署了编号为 0 至 n-1 的 n 台路由器。网络工程师通过网桥将路由器两两连接网络连通具有传递性若 A 与 B 连通、B 与 C 连通则 A 与 C 也连通。给定全部连接关系和一台目标路由器求与目标路由器连通的其他路由器数量不包含目标路由器自身。1 ≤ n ≤ 10000。每条连接 [u,v] 满足 0 ≤ u,v ≤ n-1target 满足 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((ne)α(n))空间复杂度为 O(n)。Codeimport 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); ListInteger 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); } }Gopackage 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[index1]) 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 ctype.h #include stdio.h #include stdlib.h #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机试真题PythonJSJavaGo合集】【超值优惠】Py/JS/Java/Go合集【华为od机试真题Python】Python真题题库【华为od机试真题JavaScript】JavaScript真题题库【华为od机试真题JavaGo】JavaGo真题题库【华为od机试真题C】C真题题库【华为od机试真题C语言】C语言真题题库【华为od面试手撕代码题库】面试手撕代码题库【华为od机试面试交流群】【文章底部有二维码链接可扫码加交流群】华为OD机试:二本院校有机会吗? 有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。
