[蓝桥杯基础题型] 图论题目

2024-01-01 22:38:46

遍历

添加路障

首先答案只能是0 1 2 ，原因：把出发点堵住只需要两个路障

路障为0：不能找到一条从出发点到终点的路

路障为1：能找到一条从出发点到终点的路，但是只有一条

路障为2：能找到一条从出发点到终点的路，有多条

难点：如何判断只有一条路。

  1. 原本是想用找到的那条路径，在路径上每一点都设障碍，再来看是否还有路径，时间复杂度较高。
  2. 把障碍连在一起的看成并查集，当有并查集可以把出发点和起点割开，

文章来源:https://blog.csdn.net/weixin_73512213/article/details/135295773
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。