MENU

Tarjan算法与无/有向图连通性

// tarjan算法求无向图的桥、边双连通分量并缩点
#include<cstdio>
int n, m, tot = 1, num, dcc, tc = 1, head[100010], ver[200010], Next[200010], dfn[100010], low[100010], c[100010], hc[100010], vc[200010], nc[200010], bridge[200010];
void add(int x, int y) { ver[++tot] = y, Next[tot] = head[x], head[x] = tot; }
void add_c(int x, int y) { vc[++tc] = y, nc[tc] = hc[x], hc[x] = tc; }
void tarjan(int x, int in_edge) {
    dfn[x] = low[x] = ++num;
    for (int i = head[x]; i; i = Next[i]) {
        int y = ver[i];
        if (!dfn[y]) {
            tarjan(y, i);
            if (low[x] > low[y])low[x] = low[y];
            if (low[y] > dfn[x])bridge[i] = bridge[i ^ 1] = 1;
        }
        else if (i != (in_edge ^ 1) && low[x] > dfn[y])low[x] = dfn[y];
    }
}
void dfs(int x) {
    c[x] = dcc;
    for (int i = head[x]; i; i = Next[i]) {
        int y = ver[i];
        if (c[y] || bridge[i]) continue;
        dfs(y);
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, x, y; i <= m; ++i)scanf("%d%d", &x, &y), add(x, y), add(y, x);
    for (int i = 1; i <= n; ++i)if (!dfn[i]) tarjan(i, 0);
    for (int i = 2; i < tot; i += 2)if (bridge[i])printf("%d %d\n", ver[i ^ 1], ver[i]);
    for (int i = 1; i <= n; ++i)if (!c[i])++dcc, dfs(i);
    printf("There are %d e-DCCs.\n", dcc);
    for (int i = 1; i <= n; ++i)printf("%d belongs to DCC %d.\n", i, c[i]);
    for (int i = 2, x, y; i <= tot; ++i) {
        x = ver[i ^ 1], y = ver[i];
        if (c[x] == c[y]) continue;
        add_c(c[x], c[y]);
    }
    printf("缩点之后的森林,点数 %d,边数 %d\n", dcc, tc / 2);
    for (int i = 2; i < tc; i += 2)printf("%d %d\n", vc[i ^ 1], vc[i]);
}
// tarjan算法求无向图的割点、点双连通分量并缩点
#include<cstdio>
#include<vector>
int head[100010], ver[200010], Next[200010], dfn[100010], low[100010], stack[100010], new_id[100010], c[100010], n, m, tot = 1, num, root, top, cnt, tc = 1, cut[100010], hc[100010], vc[200010], nc[200010];
std::vector<int> dcc[100010];
void add(int x, int y) { ver[++tot] = y, Next[tot] = head[x], head[x] = tot; }
void add_c(int x, int y) { vc[++tc] = y, nc[tc] = hc[x], hc[x] = tc; }
void tarjan(int x) {
    dfn[x] = low[x] = ++num, stack[++top] = x;
    if (x == root && head[x] == 0) { dcc[++cnt].push_back(x); return; } // 孤立点
    int flag = 0, y, z;
    for (int i = head[x]; i; i = Next[i]) {
        y = ver[i];
        if (!dfn[y]) {
            tarjan(y);
            if (low[x] > low[y])low[x] = low[y];
            if (low[y] >= dfn[x]) {
                ++flag, ++cnt;
                if (x != root || flag > 1) cut[x] = 1;
                do z = stack[top--], dcc[cnt].push_back(z); while (z != y);
                dcc[cnt].push_back(x);
            }
        }
        else if (low[x] > dfn[y])low[x] = dfn[y];
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, x, y; i <= m; ++i) {
        scanf("%d%d", &x, &y);
        if (x == y)continue;
        add(x, y), add(y, x);
    }
    for (int i = 1; i <= n; ++i)if (!dfn[i])root = i, tarjan(i);
    for (int i = 1; i <= n; ++i)if (cut[i])printf("%d ", i);
    puts("are cut-vertexes");
    for (int i = 1; i <= cnt; puts(""), ++i) {
        printf("v-DCC #%d:", i);
        for (int j = 0; j < dcc[i].size(); ++j)printf(" %d", dcc[i][j]);
    }
    // 给每个割点一个新的编号(编号从cnt+1开始)
    num = cnt;
    for (int i = 1; i <= n; ++i)if (cut[i])new_id[i] = ++num;
    // 建新图,从每个v-DCC到它包含的所有割点连边
    for (int i = 1, x; i <= cnt; ++i)for (int j = 0; j < dcc[i].size(); ++j)cut[x = dcc[i][j]] ? add_c(i, new_id[x]), add_c(new_id[x], i) : (void)(c[x] = i); // 除割点外,其它点仅属于1个v-DCC
    printf("缩点之后的森林,点数 %d,边数 %d\n", num, tc / 2);
    printf("编号 1~%d 的为原图的v-DCC,编号 >%d 的为原图割点\n", cnt, cnt);
    for (int i = 2; i < tc; i += 2)printf("%d %d\n", vc[i ^ 1], vc[i]);
}
// Tarjan算法求有向图强连通分量并缩点
#include<cstdio>
#include<vector>
using namespace std;
int ver[1000010], Next[1000010], head[100010], dfn[100010], low[100010], stack[100010], ins[100010], c[100010], vc[1000010], nc[1000010], hc[100010], tc, n, m, tot, num, top, cnt, x, y;
vector<int> scc[100010];
void add(int x, int y) { ver[++tot] = y, Next[tot] = head[x], head[x] = tot; }
void add_c(int x, int y) { vc[++tc] = y, nc[tc] = hc[x], hc[x] = tc; }
void tarjan(int x) {
    dfn[x] = low[x] = ++num, stack[++top] = x, ins[x] = 1;
    for (int i = head[x]; i; i = Next[i])if (!dfn[ver[i]]) {
            tarjan(ver[i]);
            if (low[x] > low[ver[i]])low[x] = low[ver[i]];
        }
    else if (ins[ver[i]] && low[x] > dfn[ver[i]])low[x] = dfn[ver[i]];
    if (dfn[x] == low[x]) {
        ++cnt;
        do y = stack[top--], ins[y] = 0, c[y] = cnt, scc[cnt].push_back(y); while (x != y);
    }
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i)scanf("%d%d", &x, &y), add(x, y);
    for (int i = 1; i <= n; ++i)if (!dfn[i])tarjan(i);
    for (int x = 1; x <= n; ++x)for (int i = head[x]; i; i = Next[i]) {
        y = ver[i];
        if (c[x] == c[y])continue;
        add_c(c[x], c[y]);
    }
}
Leave a Comment

captcha
请输入验证码