目录题目思路Code题目城市供水管道由若干个连接外部的源头水站以及内部水站、水管组成。全市共有 n 个水站编号为 0 至 n-1。供水网络由若干管道连接管道分为两类1. 单向管道Type 0水流只能从水站 u 流向水站 v2. 双向管道Type 1水流可以在水站 u 和 v 之间双向流动。受战争影响城市中的一部分供水管道破裂导致部分水站无法获得供水我们将这些无法从任一源头水站到达的水站称为孤立站。假设源头站一定有水并且源头站本身不算孤立站请你根据输入的各个水站的联通情况输出孤立站的列表结果按编号从小到大排列。输入1. n整型水站数量水站编号为 0 至 n-10 n 100002. sources整型数组数组元素为源头水站编号3. pipes二维数组数组元素为 [u, v, type]表示水站连通关系其中 u、v 为水站编号type 为连通类型- [u, v, 0] 表示单向管道水可由 u 流向 v不可由 v 流向 u- [u, v, 1] 表示双向管道水可由 u 流向 v也可由 v 流向 u。输出孤立站列表类型为整型数组数组元素为孤立站编号结果从小到大排列。输入描述输入为一行格式为n,sources,pipes其中1. n 是整数2. sources 是形如 [1,3] 的整型数组3. pipes 是形如 [[1,0,0],[1,2,0]] 的二维数组。输出描述输出孤立站编号数组按从小到大排列。若不存在孤立站则输出 []。样例1输入5,[1],[[1,0,0],[1,2,0]]输出[3,4]说明源头站为 1。由 1 可以到达 0 和 2因此 0、1、2 都不是孤立站。水站 3 和 4 无法从任一源头站到达所以输出 [3,4]。思路1.经典的BFS/DFS 图类型的题目。2.把所有水站看成图上的点把管道看成边。3.单向管道就加一条有向边双向管道就加两条相反方向的边。然后从所有 sources 同时出发做一次 BFS 或 DFS把所有能被源头水站到达的点标记出来。4.最后遍历 0 ~ n-1所有没有被访问到的水站就是孤立站按编号顺序收集输出即可。5.题目里真正稍微麻烦一点的是输入解析因为输入是一整行 n,sources,pipes后两部分本身也带逗号所以不能直接普通 split(,)需要按“最外层逗号”切分。Codeimport java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { static class Parser { String s; int idx; Parser(String s) { this.s s; this.idx 0; } // 跳过空格避免输入中夹杂空白字符影响解析。 void skipSpaces() { while (idx s.length() Character.isWhitespace(s.charAt(idx))) { idx; } } // 解析一个整数支持非负数。 int parseInt() { skipSpaces(); int num 0; while (idx s.length() Character.isDigit(s.charAt(idx))) { num num * 10 (s.charAt(idx) - 0); idx; } return num; } // 解析形如 [1,2,3] 的一维数组。 ListInteger parseIntArray() { skipSpaces(); ListInteger result new ArrayList(); idx; // 跳过 [ skipSpaces(); if (idx s.length() s.charAt(idx) ]) { idx; return result; } while (true) { result.add(parseInt()); skipSpaces(); if (s.charAt(idx) ,) { idx; continue; } if (s.charAt(idx) ]) { idx; break; } } return result; } // 解析形如 [[u,v,t],[u,v,t]] 的二维数组。 Listint[] parsePipeArray() { skipSpaces(); Listint[] result new ArrayList(); idx; // 跳过 [ skipSpaces(); if (idx s.length() s.charAt(idx) ]) { idx; return result; } while (true) { ListInteger item parseIntArray(); result.add(new int[]{item.get(0), item.get(1), item.get(2)}); skipSpaces(); if (idx s.length() s.charAt(idx) ,) { idx; continue; } if (idx s.length() s.charAt(idx) ]) { idx; break; } } return result; } } public static void main(String[] args) throws Exception { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); String line br.readLine(); // 没有输入时按空数组处理。 if (line null || line.trim().isEmpty()) { System.out.print([]); return; } // 先拆出最外层的三个部分n、sources、pipes。 ListString parts new ArrayList(); int start 0; int depth 0; for (int i 0; i line.length(); i) { char ch line.charAt(i); if (ch [) depth; else if (ch ]) depth--; else if (ch , depth 0) { parts.add(line.substring(start, i).trim()); start i 1; } } parts.add(line.substring(start).trim()); int n Integer.parseInt(parts.get(0)); Parser sourceParser new Parser(parts.get(1)); Parser pipeParser new Parser(parts.get(2)); ListInteger sources sourceParser.parseIntArray(); Listint[] pipes pipeParser.parsePipeArray(); // 建图单向边加一条双向边加两条。 ListListInteger graph new ArrayList(); for (int i 0; i n; i) { graph.add(new ArrayList()); } for (int[] pipe : pipes) { int u pipe[0], v pipe[1], type pipe[2]; graph.get(u).add(v); if (type 1) { graph.get(v).add(u); } } // 从所有源头站同时做 BFS标记可达站点。 boolean[] visited new boolean[n]; QueueInteger queue new LinkedList(); for (int source : sources) { if (!visited[source]) { visited[source] true; queue.offer(source); } } while (!queue.isEmpty()) { int node queue.poll(); for (int next : graph.get(node)) { if (!visited[next]) { visited[next] true; queue.offer(next); } } } // 所有不可达站点就是孤立站。 StringBuilder sb new StringBuilder(); sb.append([); boolean first true; for (int i 0; i n; i) { if (!visited[i]) { if (!first) { sb.append(,); } sb.append(i); first false; } } sb.append(]); System.out.print(sb.toString()); } }Gopackage main import ( bufio fmt os strings unicode ) type Parser struct { s string idx int } // 跳过空格避免输入中夹杂空白字符时影响解析。 func (p *Parser) skipSpaces() { for p.idx len(p.s) unicode.IsSpace(rune(p.s[p.idx])) { p.idx } } // 解析一个整数。 func (p *Parser) parseInt() int { p.skipSpaces() num : 0 for p.idx len(p.s) p.s[p.idx] 0 p.s[p.idx] 9 { num num*10 int(p.s[p.idx]-0) p.idx } return num } // 解析形如 [1,3] 的一维数组。 func (p *Parser) parseIntArray() []int { p.skipSpaces() result : make([]int, 0) p.idx // 跳过 [ p.skipSpaces() if p.idx len(p.s) p.s[p.idx] ] { p.idx return result } for { result append(result, p.parseInt()) p.skipSpaces() if p.s[p.idx] , { p.idx continue } if p.s[p.idx] ] { p.idx break } } return result } // 解析形如 [[u,v,t],[u,v,t]] 的二维数组。 func (p *Parser) parsePipeArray() [][]int { p.skipSpaces() result : make([][]int, 0) p.idx // 跳过 [ p.skipSpaces() if p.idx len(p.s) p.s[p.idx] ] { p.idx return result } for { result append(result, p.parseIntArray()) p.skipSpaces() if p.idx len(p.s) p.s[p.idx] , { p.idx continue } if p.idx len(p.s) p.s[p.idx] ] { p.idx break } } return result } func main() { reader : bufio.NewReader(os.Stdin) line, _ : reader.ReadString(\n) line strings.TrimSpace(line) // 没有输入时按空数组输出。 if line { fmt.Print([]) return } // 按最外层逗号切出 n、sources、pipes 三部分。 parts : make([]string, 0) start : 0 depth : 0 for i, ch : range line { if ch [ { depth } else if ch ] { depth-- } else if ch , depth 0 { parts append(parts, strings.TrimSpace(line[start:i])) start i 1 } } parts append(parts, strings.TrimSpace(line[start:])) nParser : Parser{s: parts[0]} n : nParser.parseInt() sourceParser : Parser{s: parts[1]} pipeParser : Parser{s: parts[2]} sources : sourceParser.parseIntArray() pipes : pipeParser.parsePipeArray() // 建图单向边加一条双向边加两条。 graph : make([][]int, n) for _, pipe : range pipes { u, v, typ : pipe[0], pipe[1], pipe[2] graph[u] append(graph[u], v) if typ 1 { graph[v] append(graph[v], u) } } // 从所有源头站同时做 BFS。 visited : make([]bool, n) queue : make([]int, 0) for _, source : range sources { if !visited[source] { visited[source] true queue append(queue, source) } } for head : 0; head len(queue); head { node : queue[head] for _, next : range graph[node] { if !visited[next] { visited[next] true queue append(queue, next) } } } // 输出所有未访问到的站点。 var sb strings.Builder sb.WriteString([) first : true for i : 0; i n; i { if !visited[i] { if !first { sb.WriteString(,) } sb.WriteString(fmt.Sprintf(%d, i)) first false } } sb.WriteString(]) fmt.Print(sb.String()) }C#include stdio.h #include string.h #include stdlib.h #include ctype.h #define MAXN 10005 #define MAXM 40005 #define MAXLINE 200000 typedef struct { int to; int next; } Edge; char s[MAXLINE]; int idxPtr; Edge edges[MAXM]; int head[MAXN]; int edgeCnt 0; /* 跳过空白字符避免空格影响解析。 */ void skipSpaces() { while (s[idxPtr] isspace((unsigned char)s[idxPtr])) { idxPtr; } } /* 解析一个整数。 */ int parseInt() { skipSpaces(); int num 0; while (s[idxPtr] isdigit((unsigned char)s[idxPtr])) { num num * 10 (s[idxPtr] - 0); idxPtr; } return num; } /* 加一条有向边 u - v。 */ void addEdge(int u, int v) { edges[edgeCnt].to v; edges[edgeCnt].next head[u]; head[u] edgeCnt; } /* 解析一维数组 [a,b,c]。 */ void parseIntArray(int *arr, int *size) { skipSpaces(); (*size) 0; idxPtr; /* 跳过 [ */ skipSpaces(); if (s[idxPtr] ]) { idxPtr; return; } while (1) { arr[(*size)] parseInt(); skipSpaces(); if (s[idxPtr] ,) { idxPtr; continue; } if (s[idxPtr] ]) { idxPtr; break; } } } /* 解析 pipes 二维数组并直接建图。 */ void parsePipeArray() { skipSpaces(); idxPtr; /* 跳过 [ */ skipSpaces(); if (s[idxPtr] ]) { idxPtr; return; } while (1) { int item[3], size 0; parseIntArray(item, size); int u item[0], v item[1], type item[2]; addEdge(u, v); if (type 1) { addEdge(v, u); } skipSpaces(); if (s[idxPtr] ,) { idxPtr; continue; } if (s[idxPtr] ]) { idxPtr; break; } } } int main() { if (!fgets(s, sizeof(s), stdin)) { printf([]); return 0; } /* 初始化邻接表。 */ for (int i 0; i MAXN; i) { head[i] -1; } idxPtr 0; /* 解析最前面的 n。 */ int n parseInt(); skipSpaces(); if (s[idxPtr] ,) idxPtr; /* 解析 sources。 */ int sources[MAXN], sourceCount 0; parseIntArray(sources, sourceCount); skipSpaces(); if (s[idxPtr] ,) idxPtr; /* 解析 pipes 并建图。 */ parsePipeArray(); /* 从所有源头站同时做 BFS。 */ int visited[MAXN] {0}; int queue[MAXN]; int front 0, rear 0; for (int i 0; i sourceCount; i) { int source sources[i]; if (!visited[source]) { visited[source] 1; queue[rear] source; } } while (front rear) { int node queue[front]; for (int e head[node]; e ! -1; e edges[e].next) { int next edges[e].to; if (!visited[next]) { visited[next] 1; queue[rear] next; } } } /* 输出所有不可达站点。 */ printf([); int first 1; for (int i 0; i n; i) { if (!visited[i]) { if (!first) { printf(,); } printf(%d, i); first 0; } } printf(]); 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。让他帮助你查询原因。