本文从WordPress迁移而来, 查看全部WordPress迁移文章
仙人掌图的定义(有向图和无向图略有不同)
有向图:
- 是一个强连通图
- 每条有向边都属于且仅属于一个环
无向图
- 是一个连通图
- 每条无向边至多属于一个环(即有些无向边可以不属于任何一个环)
在看完定义后,思考10分钟让让在纸上画一些满足定义要求的图,画完后就能明白为什么这种图叫仙人掌图
Sample
有向图中的仙人掌图
无向图中的仙人掌图
仙人掌图的判定(包括有向图和无向图)
有向cactus的判定:(三者同时满足的为有向cactus)
- 图中没有横叉边(搞清楚树边,横叉边,后向边
- 在dfs遍历中,对于任意点v为点u的儿子,则满足low[v] <= dfn[u]
- 设置一个量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,用反证法证明
假设存在一个有向cactus,对于点u存在两条或更多的后向边,即b[u] >= 2,分别指向u的祖先x和祖先y(x!=y),先约定祖先x是祖先y的祖先,则存在2个环:
- x -> u -> x
y -> u -> y
又因为x是y的祖先,所以还存在x -> y
可知y -> u这部分路径上的边都属于2个环,和有向cactus的定义矛盾。因而点u最多只存在一条后向边
假设存在一个有向cactus,对于点u存在两个儿子v和vv,它们都满足low[v] < dfn[u],low[vv] < dfn[u]。即v和vv都可以回到点u的祖先,设v可回到祖先x,点vv可回到祖先y。若x和y为不同点,则约定x是y的祖先。那么存在2个环:
- y -> u -> vv -> y
x -> u -> v -> x
又因为x是y祖先(若两者为不同点),还存在x->y
那么可知,无论x = y还是x != y,y -> u部分的路径上的边都存在于2个环内,与有向cactus的定义矛盾。因为点u最多只存在一个孩子v,满足low[v] < dfn[u]
假设存在一个有向cactus,对于点u,存在一条后向边,并且存在一个儿子v,满足low[v] < dfn[u]。假设点u通过后向边可以回到祖先x,儿子v可以回到祖先y,若x和y不同,则约定x为y的祖先。那么会形成2个环:
- x -> u -> x
y -> u -> v -> y
若x != y,还存在x -> y,可以y -> u部分的路径上的边属于2个环,与有向cactus定义矛盾。
无向cactus的判定:
无向cactus的判定比较简单,直接从定义出发。对于给定的无向图,我们计算出图中每条边属于多少个环。若存在一条或更多的边,属于2个或更多的环,那么这个无向图不是cactus。
怎么判断无向图中每条边分别属于多少个环:LCA + DP
- 首先对无向图进行dfs,得到dfs树。在dfs过程若遇到可成环的边,就把它保存下来
- dfs结束后得到树,对已之前保存的每条成环边,若添加到dfs树中,必使树出现环,成环部分就是 u -> LCA(u,v) -> v -> u,我们就给这个环上的每条边计数。
- 计数的具体做法是利用树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