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分析

题目思路

这道题就是求二维矩阵的连通块个数,或者是说大家比较熟悉的“岛屿问题”。我们只需遍历整个图,每次以一个未被遍历过的图为起点,用dfs或bfs

将与它相连通的点统计起来,我们可以用并查集判断两个点时候联通。但在这份题解中,我们直接将联通的点放入一个集合中,也能达到目的,不过相较于

并查集时间复杂度会稍高,同时采用dfs遍历。

题解

P1062.2022.11.3-计算快递主站点

    1000ms Tried: 96 Accepted: 46 Difficulty: 5
    算法与标签>DFS

题目描述

塔子哥最近扩展了快递服务,快递业务范围有 NNN 个站点,如果 AAA 站点与 BBB 站点可以中转快递,则认为 A−BA-BA−B 站可达,如果 A−BA-BA−B 可达, B−CB-CB−C 可达,则 A−CA-CA−C 可达。现在给 NNN 个站点编号 0、1、…n−10、1、…n-10、1、…n−1 ,用 s[i][j]s[i][j]s[i][j] 表示 i−ji-ji−j 是否可达, s[i][j]=1s[i][j]=1s[i][j]=1 表示 i−ji-ji−j 可达, s[i][j]=0s[i][j]=0s[i][j]=0 表示 i−ji-ji−j 不可达。

塔子哥才刚刚开展快递服务,不太知道需要多少个主站点才能覆盖所以的站点,现用二维数组,给定 NNN 个站点的可达关系,你能帮塔子哥计算至少选择从几个主站点出发,才能可达所有站点吗?(覆盖所有站点业务)。

输入描述

第一行输入为 NNN , NNN 表示站点个数。
之后N行表示站点之间的可达关系,第i行第j个数值表示编号为i和j之间是否可达。

输出描述

输出站点个数,表示至少需要多少个主站点。

补充说明

1 < N < 10000

样例

输入

4
1 1 1 1
1 1 1 0
1 1 1 0
1 0 0 1

输出

1

登录后即可使用 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, 21ms
  3. Powered by Hydro v5.0.0-beta.18 Community
CLOSE


ScanQRCodePrompt

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

Forgot password or username?