解题思路
把每个水站看成图中的一个点,把每条管道看成图中的边。
对于管道 [u,v,type]:
- 当 type=0 时,表示水只能从 u 流向 v,因此只加入一条有向边 u→v。
- 当 type=1 时,表示水可以双向流动,因此加入两条有向边 u→v 和 v→u。
P14187.寻找孤立水站(200分)
题目内容
城市供水管道由若干个连接外部的源头水站,以及内部水站、水管组成。
全市共有 n 个水站,编号为 0 至 n−1。
供水网络由若干管道连接,管道分为两类:
- 单向管道 (Type 0):水流只能从水站 u 流向水站 v。
- 双向管道 (Type 1):水流可以在水站 u 和 v 之间双向流动。
受战争影响,城市中的一部分供水管道破裂导致部分水站无法获得供水,我们称为孤立站。
假设源头站一定有水(非孤立站),请你根据输入的各个水站的联通情况,输出孤立站的列表,从小到大进行排列。
输入描述
n:整型,水站数量,水站编号为 0 至 n−1,0<n≤10000;
sources:整型数组,数组元素为源头水站编号;
pipes:二维数组,数组元素为 [u,v,type],表示水站连通关系,其中 u,v 为水站编号,type 为连通类型。
-
[u,v,0] 表示:单向管道,水可由u流向v,不可由v流向u
-
[u,v,1] 表示:双向管道,水可由u流向v,也可由v流向u
输出描述
孤立站列表,类型为整型数组,数组元素为孤立站编号,结果从小到大排列。
样例1
输入
5,[1],[[1,0,0],[1,2,0]]
输出
[3,4]
说明
1 号为源头站,从 1 号到 0 号和 2 号都有单向流动,3 号、4 号为孤立站。
样例2
输入
5,[0,1],[[0,2,0],[0,3,0],[4,3,0]]
输出
[4]
说明
0 号、1 号是源头站,0、1 非孤立站;
0 号向 2 号和 3 号是单向流通,2、3 非孤立站;
4 号向 3 号单向流通,但是无水站向 4 号供水,4 是孤立站。
样例3
输入
5,[0],[[0,1,1],[0,2,1],[3,2,1],[4,2,1]]
输出
[]
说明
0 号站到 1 号、2 号为双向流通,1、2 非孤立站;
3 号、4 号到 2 号为双向流通,3、4 非孤立站;
所以系统无孤立站。