仙人掌图的判定

本文从WordPress迁移而来, 查看全部WordPress迁移文章

仙人掌图的定义(有向图和无向图略有不同)

有向图:

  1. 是一个强连通图
  2. 每条有向边都属于且仅属于一个环

无向图

  1. 是一个连通图
  2. 每条无向边至多属于一个环(即有些无向边可以不属于任何一个环)

在看完定义后,思考10分钟让让在纸上画一些满足定义要求的图,画完后就能明白为什么这种图叫仙人掌图

Sample

  • 有向图中的仙人掌图

  • 无向图中的仙人掌图

仙人掌图的判定(包括有向图和无向图)

有向cactus的判定:(三者同时满足的为有向cactus)

  1. 图中没有横叉边(搞清楚树边,横叉边,后向边
  2. 在dfs遍历中,对于任意点v为点u的儿子,则满足low[v] <= dfn[u]
  3. 设置一个量a[u]表示u的儿子v中满足low[v] < dfn[u]的个数;一个量b[u]表示u的后向边的条数,则a[u] + b[u] < 2

对于判定1:

如果存在横叉边,横叉边不属于任何一个环,和有向cactus定义矛盾(这是由横叉边的定义可知)

对于判定2:

反证法:假设u的儿子v在dfs后满足:low[v] > dfn[u],那么说明点v不存在后向边,无法回到u或u的祖先处,说明图不是强连通,与有向cactus定义矛盾

另外我们画图看看什么时候满足low[v] = dfn[u] 和 low[v] < dfn[u]

  • 点1为父亲,点2为儿子时,low[2] = dfn[1]
  • 点2为父亲,点3为儿子时,low[3] < dfn[2]
  • 点3为父亲,点4为儿子时,low[4] < dfn[3]
  • 点4为父亲,点5为儿子时,low[5] < dfn[4]
  • 点5为父亲,点6为儿子时,low[6] < dfn[5]
  • 而边<6,1>是后向边而非父子边,点6和点1在dfs中不是父子关系

对于判定3:a[v] + b[v] < 2,用反证法证明

  1. 假设存在一个有向cactus,对于点u存在两条或更多的后向边,即b[u] >= 2,分别指向u的祖先x和祖先y(x!=y),先约定祖先x是祖先y的祖先,则存在2个环:

    1. x -> u -> x
    2. y -> u -> y

      又因为x是y的祖先,所以还存在x -> y

      可知y -> u这部分路径上的边都属于2个环,和有向cactus的定义矛盾。因而点u最多只存在一条后向边

  2. 假设存在一个有向cactus,对于点u存在两个儿子v和vv,它们都满足low[v] < dfn[u],low[vv] < dfn[u]。即v和vv都可以回到点u的祖先,设v可回到祖先x,点vv可回到祖先y。若x和y为不同点,则约定x是y的祖先。那么存在2个环:

    1. y -> u -> vv -> y
    2. x -> u -> v -> x

      又因为x是y祖先(若两者为不同点),还存在x->y

      那么可知,无论x = y还是x != y,y -> u部分的路径上的边都存在于2个环内,与有向cactus的定义矛盾。因为点u最多只存在一个孩子v,满足low[v] < dfn[u]

  3. 假设存在一个有向cactus,对于点u,存在一条后向边,并且存在一个儿子v,满足low[v] < dfn[u]。假设点u通过后向边可以回到祖先x,儿子v可以回到祖先y,若x和y不同,则约定x为y的祖先。那么会形成2个环:

    1. x -> u -> x
    2. y -> u -> v -> y

      若x != y,还存在x -> y,可以y -> u部分的路径上的边属于2个环,与有向cactus定义矛盾。

无向cactus的判定:

无向cactus的判定比较简单,直接从定义出发。对于给定的无向图,我们计算出图中每条边属于多少个环。若存在一条或更多的边,属于2个或更多的环,那么这个无向图不是cactus。

怎么判断无向图中每条边分别属于多少个环:LCA + DP

  1. 首先对无向图进行dfs,得到dfs树。在dfs过程若遇到可成环的边,就把它保存下来
  2. dfs结束后得到树,对已之前保存的每条成环边,若添加到dfs树中,必使树出现环,成环部分就是 u -> LCA(u,v) -> v -> u,我们就给这个环上的每条边计数。
  3. 计数的具体做法是利用树DP:
    • 定义dp[u]表示树中点u的父边的计数;
    • 对已一对询问LCA(u,v),进行处理dp[u]++ ,dp[v]++ ,dp[LCA(U,V)] – 2
    • 做完所有的LCA询问后,对树再一次遍历,回溯过程中DP状态转移为dp[u] += dp[v],v为u的儿子

题目:

  • 有向cactus判定:HDU 3594
  • 无向cactus判定:POJ 2793