Tarjanテンプレートの小さなコレクション

強連結成分#

ノードを探索木のルートノード番号に色付けする：

void tarjan (int p) {
    dfn[p] = low[p] = ++tim;
    v[p] = 1;
    s.push(p);
    for (int i = head[p]; i; i = e[i].nex) {
        int y = e[i].to;
        if (!dfn[y]) {
            tarjan(y);
            low[p] = min(low[p], low[y]);
        }
        else if(v[y]){
            low[p] = min(low[p], dfn[y]);
        }
    }
    if (dfn[p] == low[p]) {
        color[p] = p;
        v[p] = 0;
        while (s.top() != p) {
            color[s.top()] = p;
            v[s.top()] = 0;
            s.pop();
        }
        s.pop();
    }
}

縮点#

板子がない。。。
多くの場合がある。時には入出次数のみを統計することもできる
時には新しいグラフを作成することもできる (namespace namespace namespace)

割点#

void tarjan (int p){
    dfn[p] = low[p] = ++tim;
    int kidsCnt = 0;
    for (int i = head[p]; i; i = e[i].nex) {
        int y = e[i].to;
        if (!dfn[y]) {
            ++kidsCnt;
            tarjan(y);
            low[p] = min(low[p], low[y]);
            if ((p == root && kidsCnt >= 2) || (p != root && dfn[p] <= low[y])) {
                cut[p] = 1;
                //++cutsCnt;会重复统计数量
            }
        }
        else {
            low[p] = min(low[p], dfn[y]);
        }
    }
}

呼び出し：

for (int i = 1; i <= n; ++i) {
    if (!dfn[i]) {
        root = i;
        tarjan(i);
    }
}

点重み連結成分#

模範問題がないので、正しいかどうかわかりません。。。

void tarjan (int p, int fa) {
    dfn[p] = low[p] = ++tim;
    for (int i = head[p]; i; i = e[i].nex) {
        int y = e[i].to;
        if (!dfn[y]) {
            st[++top] = y;
            tarjan(y, p);
            low[p] = min(low[p], low[y]);
            if (low[y] >= dfn[u]) {
                ++cnt;
                while (st[top] != y) {
                    bcc[cnt].push_back(st[top--]);
                }
                bcc[cnt].push_back(stack[top--]);
                bcc[cnt].push_back(p);
            }
        }
        else if (y != fa) {
            low[p] = min(low[p], dfn[y]);
        }
    }
}

割辺（ブリッジ）#

newpの初期値は1に設定する必要があります

void tarjan (int p, int ed) {//edは来た辺
    dfn[p] = low[p] = ++tim;
    for (int i = head[p]; i; i = e[i].nex) {
        int y = e[i].to;
        if (!dfn[y]) {
            tarjan(y, i);
            low[p] = min(low[p], low[y]);
            if (dfn[p] < low[y]) {
                bridge[i] = bridge[i ^ 1] = 1;
            }
        }
        else if (i != (ed ^ 1)) {
            low[p] = min(low[p], dfn[y]);
        }
    }
}

辺重み連結成分#

まず、ブリッジのtarjanを実行します
そして、dfsがあります

void dfs (int p) {
    dcolor[p] = dcnt;
    for (int i = head[p]; i; i = e[i].nex) {
        int y = e[i].to;
        if (dcolor[y] != 0 || bridge[i] == 1) {
            continue;
        }
        dfs(y);
    }
}

このdfsは次のように使用します

for (int i = 1; i <= n; ++i) {
    if (!dcolor[i]) {
        ++dcnt;
        dfs(i);
    }
}

連結グラフを辺重み連結グラフに変換するために必要な辺の数#

for (int i = 1; i <= m; ++i) {
    if (dcolor[e[i * 2].frm] != dcolor[e[i * 2].to]) {
        ++out[dcolor[e[i * 2].frm]];
        ++out[dcolor[e[i * 2].to]];
    }
}
int leaf = 0;
for (int i = 1; i <= dcnt; ++i) {
    if (out[i] == 1) {
        ++leaf;
    }
}
printf("%d\n", leaf ==  1 ? 0 : (leaf + 1) / 2);