本文从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