6
15
2016
0

【UER #5A】【网格图化树】【宏观估计】万圣节的南瓜灯

因为眼镜坏了就没办法写代码了(=_=)

题意:

n*m的网格,其中K个格子被弄坏。

判断该网格图是否满足:对于任意两个没有被弄坏的格子,都存在且仅存在一条连接它们的简单路径(路径上各格子相连且每个格子不重复经过)。

分析:

对于两个没有被弄坏的格子,之间的路径可能有多条、有1条、不存在。

将没有被弄坏的相邻格子连边,网格图满足条件等价于所构成的图是一棵树。(满足存在、且不存在多条)

 

 

Category: 并查集 | Tags: 基础图论 图的连通性 网格图 | Read Count: 391

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com