仙人掌

简介

希望有生之年能考一次仙人掌

点仙人掌

每个点最多属于一个简单环

边仙人掌

定义：每个边最多属于一个简单环

简单环最低点：简单环中 $dfs$ 序最小的点

简单环最高点：简单环中 $dfs$ 序最大的点

简单环边：属于某一个简单环的边，简称为简单环

简单环回边：在边仙人掌中， $dfs$ 中的回边都唯一确定了一个简单环，且我们称这个回边为这个简单环的回边。能够注意到这个回边连接最低点和最高点

判断一个图是否为边仙人掌

我们只需要每次将回边所确定的简单环都进行标记，如果在标记的时候出现重复标记则证明不是该图不是边仙人掌

注意到我们在标记的时候并没有直接标记边，而是标记的点

对于一个简单环，我们会标记除了最低点以外的其他点，注意到这样即使出现一个点属于多个简单环的情况也不会出错

因为如果多个简单环有公共点，那么这个公共点一定是某一个简单环的某个点和其它所有简单环的最低点，所以不会出现重复标记

void dfs(int u, int fa) {
    static int cnt = 0; 
    dfn[u] = ++cnt;
    for (int i = head[u]; ~i; i = e[i].next) { 
        int v = e[i].to; if (v == fa) continue;
        if (!dfn[v]) f[v] = u, dfs(v, u);
        else if (dfn[v] < dfn[u]) {
            int t = u; ++num;
            while (t != v) { 
                if (bl[t]) cout << "-1\n", exit(0);
                bl[t] = num;
                t = f[t];
            }
        }
    }
}

仙人掌dp

对于仙人掌这种类树型结构，我们需要将树边和简单环分开进行 $dp$

具体的处理方法是将简单环当成点双联通分量，使用 $tarjan$ 的那一套方法

int dfn[maxn], low[maxn];
void dfs(int u) {
    static int cnt = 0;
    dfn[u] = low[u] = ++cnt;
    f[u][0] = 0; f[u][1] = 1; 
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa[u]) continue;
        if (!dfn[v]) {
            fa[v] = u; dfs(v);
            low[u] = min(low[u], low[v]); 
        }
        else low[u] = min(low[u], dfn[v]);
        if (low[v] > dfn[u]) {
            // 在这里进行树形dp
            // 注意到如果一个点不会将其在简单环中的儿子的贡献转移到自身
        }
    }
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (u == fa[v] || dfn[v] < dfn[u]) continue;
        // 在这里特殊处理简单环，注意到我们只需要处理从最高点转移最低点的情况即可
        // 另外需要注意在这里我们只需要更新 u 的 dp 值即可，因为中间那些点都在后续的更新中并不会出现
    }
}

在简单环中，我们尝试破环为链或者用其他方法进行 $dp$ 即可

例题

bzoj 4316 小C的独立集 边仙人掌最大独立集，对于简单环我们钦定最低点选或者不选破环为链即可