寻找孤立水站更多语言题解可查看华为OD机试新系统真题 - 寻找孤立水站(C/C/Py/Java/Js/Go)题解题目描述城市供水管道由若干个连接外部的源头水站以及内部水站、水管组成。 全市共有n nn个水站编号为0 00至n − 1 n-1n−1。 供水网络由若干管道连接管道分为两类单向管道 (T y p e TypeType0 00)水流只能从水站u uu流向水站v vv。双向管道 (T y p e TypeType1 11)水流可以在水站u uu和v vv之间双向流动。受战争影响城市中的一部分供水管道破裂导致部分水站无法获得供水我们称为孤立站。假设源头站一定有水非孤立站请你根据输入的各个水站的联通情况输出孤立站的列表从小到大进行排列。输入描述n nn整型水站数量水站编号为0 00至n − 1 n-1n−10 n ≤ 10000 0 n \le 100000n≤10000s o u r c e s sourcessources整型数组数组元素为源头水站编号p i p e s pipespipes二维数组数组元素为[ u , v , t y p e ] [u, v, type][u,v,type]表示水站连通关系其中u , v u, vu,v为水站编号t y p e typetype为连通类型。[ u , v , 0 ] [u, v, 0][u,v,0]表示单向管道水可由u uu流向v vv不可由v vv流向u uu[ u , v , 1 ] [u, v, 1][u,v,1]表示双向管道水可由u uu流向v vv也可由v vv流向u uu输出描述孤立站列表类型为整型数组数组元素为孤立站编号结果从小到大排列。样例1输入5 1 1,0,0 1,2,0输出3,4说明1 11号为源头站从1 11号到0 00号和2 22号都有单向流动3 33号、4 44号为孤立站。样例2输入5 0,1 0,2,0 0,3,0 4,3,0输出4说明0 00号、1 11号是源头站0 00、1 11非孤立站0 00号向2 22号和3 33号是单向流通2 22、3 33非孤立站4 44号向3 33号单向流通但是无水站向4 44号供水4 44是孤立站。样例3输入5 0 0,1,1 0,2,1 3,2,1 4,2,1输出说明0 00号站到1 11号、2 22号为双向流通1 11、2 22非孤立站3 33号、4 44号到2 22号为双向流通3 33、4 44非孤立站所以系统无孤立站。题解思路思路BFS这道题本质是一个多源BFS扩散题。只有从所有源头开始进行BFS扩散标记访问过的水站。最终未被访问的水站就是独立站。处理逻辑如下根据给出的pipes构建临界图其中根据type决定构建单项边还是双向边。定义visited记录某个站点是否已被访问。使用队列模拟BFS扩散初始将所有源头站加入队列中并标记已访问。接下来就是典型的BFS模板做法这部分实现可参照下面代码BFS结束之后从前往后将visited未访问的站点按顺序加入结果中即可。code#includestdio.h#includestring.h#includestdlib.h#defineMAXN10005#defineMAXM200005// 邻接表inthead[MAXN];intnxt[MAXM];intto[MAXM];intedgeCnt0;voidaddEdge(intu,intv){to[edgeCnt]v;nxt[edgeCnt]head[u];head[u]edgeCnt;}// BFS队列intqueue[MAXN];intvisited[MAXN];// 字符串分割sourcesintparseSources(char*str,int*sources){intcnt0;char*tokenstrtok(str,,\n);while(token){sources[cnt]atoi(token);tokenstrtok(NULL,,\n);}returncnt;}// 解析 pipesvoidparsePipes(char*str,intn){char*tokenstrtok(str, \n);while(token){intu,v,type;sscanf(token,%d,%d,%d,u,v,type);if(type0){// 单向addEdge(u,v);}else{// 双向建边addEdge(u,v);addEdge(v,u);}tokenstrtok(NULL, \n);}}intmain(){intn;scanf(%d,n);getchar();charline1[100000],line2[100000],line3[100000];fgets(line1,sizeof(line1),stdin);fgets(line2,sizeof(line2),stdin);fgets(line3,sizeof(line3),stdin);// 初始化memset(head,-1,sizeof(head));intsources[MAXN];intsc0;// sources 输入if(strlen(line1)1){scparseSources(line1,sources);}// pipes 输入if(strlen(line2)1){parsePipes(line2,n);}// bfs进行扩散intfront0,rear0;// 将所有源放入队列并标记已访问for(inti0;isc;i){queue[rear]sources[i];visited[sources[i]]1;}while(frontrear){intcurqueue[front];for(intihead[cur];i!-1;inxt[i]){intvto[i];if(visited[v])continue;visited[v]1;queue[rear]v;}}// 输出孤立站intfirst1;for(inti0;in;i){if(!visited[i]){if(!first)printf(,);printf(%d,i);first0;}}return0;}