2021-team4-C012

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

跟pb队合训，坐牢


补齐了割点、点双的板子：

存点写法：  注意退栈结束的时机;注意以下算法结束后1不一定是真正的割点，需要特判，但不影响求点双
void tarjan(int x) {
    dfn[x] = low[x] = ++ idx, stk[++ top] = x;
    for (int k = hd[x]; k; k = e[k].nx)
        if (not e[k].f) {
            if (not dfn[e[k].v]) {
                e[k].f = e[k ^ 1].f = 1;
                tarjan(e[k].v);
                low[x] = min(low[x], low[e[k].v]);
                if (low[e[k].v] >= dfn[x]) {
                    cut[x] = 1;
                    cnt ++;
                    up[cnt] = x;
                    while (1) {
                        int y = stk[top];
                        col[y] = cnt;
                        stk[top --] = 0;
                        if (y == e[k].v)
                            break;
                    }
                }
            }
            else
                low[x] = min(low[x], dfn[e[k].v]);
        }
}

存边写法：
Leg板子上有


·对序列删除元素递归为子问题时 考虑重标号可行性

·做不动就打表 @肉眼找dp柿子大师ypl

跟pb队合训，坐牢

补齐了割点、点双的板子：

存点写法： 注意退栈结束的时机;注意以下算法结束后1不一定是真正的割点，需要特判，但不影响求点双

void tarjan(int x) {

dfn[x] = low[x] = ++ idx, stk[++ top] = x;

for (int k = hd[x]; k; k = e[k].nx)

if (not e[k].f) {

if (not dfn[e[k].v]) {

e[k].f = e[k ^ 1].f = 1;

tarjan(e[k].v);

low[x] = min(low[x], low[e[k].v]);

if (low[e[k].v] >= dfn[x]) {

cut[x] = 1;

cnt ++;

up[cnt] = x;

while (1) {

int y = stk[top];

col[y] = cnt;

stk[top --] = 0;

if (y == e[k].v)

break;

}

}

}

else

low[x] = min(low[x], dfn[e[k].v]);

}

}

存边写法：

Leg板子上有

·对序列删除元素递归为子问题时 考虑重标号可行性

·做不动就打表 @肉眼找dp柿子大师ypl