1. Job Roadmap
  2. Home
  3. Problem Set
  4. codenotelist
  5. Forum
  6. course
  7. Shore Share Sessions
  8. Record
  1. Login
  2. Sign Up
  3. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
    ZhContent TextSol AI分析

解题思路

把每个水站看成图中的一个点,把每条管道看成图中的边。

对于管道 [u,v,type][u, v, type][u,v,type]:

  • 当 type=0type = 0type=0 时,表示水只能从 uuu 流向 vvv,因此只加入一条有向边 u→vu \to vu→v。
  • 当 type=1type = 1type=1 时,表示水可以双向流动,因此加入两条有向边 u→vu \to vu→v 和 v→uv \to uv→u。

P14187.寻找孤立水站(200分)

    1000ms Tried: 43 Accepted: 15 Difficulty: 5 所属公司 : 华为od
    算法与标签>BFS

题目内容

城市供水管道由若干个连接外部的源头水站,以及内部水站、水管组成。 全市共有 nnn 个水站,编号为 000 至 n−1n-1n−1。 供水网络由若干管道连接,管道分为两类:

  • 单向管道 (TypeTypeType 000):水流只能从水站 uuu 流向水站 vvv。
  • 双向管道 (TypeTypeType 111):水流可以在水站 uuu 和 vvv 之间双向流动。

受战争影响,城市中的一部分供水管道破裂导致部分水站无法获得供水,我们称为孤立站。

假设源头站一定有水(非孤立站),请你根据输入的各个水站的联通情况,输出孤立站的列表,从小到大进行排列。

输入描述

nnn:整型,水站数量,水站编号为 000 至 n−1n-1n−1,0<n≤100000 < n \le 100000<n≤10000;

sourcessourcessources:整型数组,数组元素为源头水站编号;

pipespipespipes:二维数组,数组元素为 [u,v,type][u, v, type][u,v,type],表示水站连通关系,其中 u,vu, vu,v 为水站编号,typetypetype 为连通类型。

  • [u,v,0][u, v, 0][u,v,0] 表示:单向管道,水可由uuu流向vvv,不可由vvv流向uuu

  • [u,v,1][u, v, 1][u,v,1] 表示:双向管道,水可由uuu流向vvv,也可由vvv流向uuu

输出描述

孤立站列表,类型为整型数组,数组元素为孤立站编号,结果从小到大排列。

样例1

输入

5,[1],[[1,0,0],[1,2,0]]

输出

[3,4]

说明

111 号为源头站,从 111 号到 000 号和 222 号都有单向流动,333 号、444 号为孤立站。

样例2

输入

5,[0,1],[[0,2,0],[0,3,0],[4,3,0]]

输出

[4]

说明

000 号、111 号是源头站,000、111 非孤立站;

000 号向 222 号和 333 号是单向流通,222、333 非孤立站;

444 号向 333 号单向流通,但是无水站向 444 号供水,444 是孤立站。

样例3

输入

5,[0],[[0,1,1],[0,2,1],[3,2,1],[4,2,1]]

输出

[]

说明

000 号站到 111 号、222 号为双向流通,111、222 非孤立站;

333 号、444 号到 222 号为双向流通,333、444 非孤立站;

所以系统无孤立站。

登录后即可使用 AI 分析。

模式
倒计时时长
:

最长 10 小时 59 分;应用后按此时长重新开始。

提示:点击提交记录在左侧题面区域查看详情
题库
AI分析设置
留空使用官方API Key,每天有次数限制(自定义API Key仅限会员和管理员使用,不限次数)
会员和管理员可切换模型;切到 Kimi/智谱/通义/豆包时需填写对应供应商 API Key
升级会员,可将运行与提交冷却时间缩短至 1 秒起

Status

  • Judging Queue
  • Service Status

Development

  • Open Source

Support

  • Help
  • Contact Us

About

  • About
  • Privacy
  • Terms of Service
  • Copyright Complaint
  1. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
  2. Legacy mode
  3. Theme
    1. Light
    2. Dark
  1. 京ICP备2025123107号-1
  2. Worker 0, 48ms
  3. Powered by Hydro v5.0.0-beta.18 Community
CLOSE


ScanQRCodePrompt

请使用微信扫描下方二维码完成注册

Forgot password or username?