寻找孤立水站
更多语言题解可查看：华为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−1，0 < n ≤ 10000 0 < n \le 100000<n≤10000；
s 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
#include<stdio.h>#include<string.h>#include<stdlib.h>#defineMAXN10005#defineMAXM200005// 邻接表inthead[MAXN];intnxt[MAXM];intto[MAXM];intedgeCnt=0;voidaddEdge(intu,intv){to[edgeCnt]=v;nxt[edgeCnt]=head[u];head[u]=edgeCnt++;}// BFS队列intqueue[MAXN];intvisited[MAXN];// 字符串分割：sourcesintparseSources(char*str,int*sources){intcnt=0;char*token=strtok(str,",\n");while(token){sources[cnt++]=atoi(token);token=strtok(NULL,",\n");}returncnt;}// 解析 pipesvoidparsePipes(char*str,intn){char*token=strtok(str," \n");while(token){intu,v,type;sscanf(token,"%d,%d,%d",&u,&v,&type);if(type==0){// 单向addEdge(u,v);}else{// 双向建边addEdge(u,v);addEdge(v,u);}token=strtok(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];intsc=0;// sources 输入if(strlen(line1)>1){sc=parseSources(line1,sources);}// pipes 输入if(strlen(line2)>1){parsePipes(line2,n);}// bfs进行扩散intfront=0,rear=0;// 将所有源放入队列，并标记已访问for(inti=0;i<sc;i++){queue[rear++]=sources[i];visited[sources[i]]=1;}while(front<rear){intcur=queue[front++];for(inti=head[cur];i!=-1;i=nxt[i]){intv=to[i];if(visited[v])continue;visited[v]=1;queue[rear++]=v;}}// 输出孤立站intfirst=1;for(inti=0;i<n;i++){if(!visited[i]){if(!first)printf(",");printf("%d",i);first=0;}}return0;}
