P6966 [NEERC2016]Cactus Construction

zhylj · 2021-10-28 19:29:37 · 题解

先考虑树的情况如何构造：

我们考虑从叶子开始由深至浅合并子树，我们让三种颜色分别代表三个意义：

• 颜色 1：与这个点相邻的边均已建好。
• 颜色 2：以这个点为根的整个子树都已建好，但它和它的父亲还未连边。
• 颜色 3：以这个点为根的整个子树还没建好。

显然，一开始所有点的颜色都要设为 3，然后我们按深度从大到小考虑每个点 u，将其和其所有孩子 v 连边，完成这棵子树的构造，由于我们考虑的顺序，所以此时其所有孩子的颜色均为 2。故可以依次进行以下的步骤：

• 将 u,v 合并。
• 连接所有颜色 3 和颜色 2 的点。
• 将颜色 2 改为颜色 1。

在考虑完所有孩子后，我们就可以将 u 的颜色 3 改为颜色 2 了。

接下来我们考虑仙人掌的构造：找出一棵 DFS 树，那么就有：每条边只被至多一个非树边覆盖、每条非树边均为返祖边。于是考虑利用颜色 4 表示还未连返祖边的点。

那么在考虑点 u 时，其所有孩子 v 一共有三种情况（注意在每次拼接开始时，u,v 分别都为连通块中唯一的颜色为 3,2 的点）：

然后就做完了，操作数是 \mathcal O(n) 的，较为宽裕。

const int N = 1e6 + 5;

int n, o_cnt;
char opt[N][20];

std::vector <int> E[N];
void Add(int u, int v) {
    E[u].push_back(v);
    E[v].push_back(u);
}

int dep[N], fa[N], low[N];
bool is_bg[N];
std::vector <int> ch[N], dfa;
void Dfs(int u) {
    dep[u] = dep[fa[u]] + 1;
    low[u] = dep[u];
    for(int v : E[u])
        if(v != fa[u]) {
            if(!dep[v]) {
                ch[u].push_back(v);
                fa[v] = u; Dfs(v);
                low[u] = std::min(low[u], low[v]);
            } else if(dep[v] < dep[u]) {
                low[u] = std::min(low[u], dep[v]);
                is_bg[u] = true;
            }
        }
    dfa.push_back(u);
}
void Solve() {
    for(int u : dfa) {
        sprintf(opt[++o_cnt], "r %d 1 3", u);
        std::sort(ch[u].begin(), ch[u].end(), [&](const int &x, const int &y) {
            return low[x] > low[y];
        });
        for(int v : ch[u]) {
            sprintf(opt[++o_cnt], "j %d %d", u, v);
            sprintf(opt[++o_cnt], "c %d 2 3", u);
            if(low[v] < dep[u] && is_bg[v]) {
                sprintf(opt[++o_cnt], "r %d 2 4", v);
            } else {
                if(low[v] == dep[u]) {
                    sprintf(opt[++o_cnt], "c %d 3 4", u);
                    sprintf(opt[++o_cnt], "r %d 4 1", u);
                }
                sprintf(opt[++o_cnt], "r %d 2 1", v);
            }
        }
        sprintf(opt[++o_cnt], "r %d 3 2", u);
    }
}

int main() {
    int m; scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i) {
        int k; scanf("%d", &k);
        std::vector <int> p;
        while(k--) { int x; scanf("%d", &x); p.push_back(x); }
        for(int j = 0; j < (int)p.size() - 1; ++j)
            Add(p[j], p[j + 1]);
    }
    Dfs(1);
    Solve();
    printf("%d\n", o_cnt);
    for(int i = 1; i <= o_cnt; ++i)
        printf("%s\n", opt[i]);
    return 0;
}