无向图割点（割顶）、桥（边的双接通分量+缩点）

无向图割点（割顶）、桥（边的双连通分量+缩点）
求割顶(割点)，主要的算法结构就是DFS，一个点是割点，当且仅当以下两种情况:
(1)该节点是根节点，且有两棵以上的子树

(2)该节点的子节点中的任一个，没有到该节点祖先的反向边（就是说如果没有这个割顶，那么这个子节点和那个祖先之间就不能连通）

代码：（按照不连通图，同样适用与连通图）

const int MAXN = 102;
int n, ans, cc;
vector<int> g[MAXN];
bool vis[MAXN];
int low[MAXN], dfn[MAXN], f[MAXN];

void dfs(int u, int depth, const int root) {
    dfn[u] = low[u] = depth;
    visited[u] = true;
    int cnt = 0;
    for (unsigned int i=0; i<g[u].size(); i++) {
        int j = g[u][i];
        if (!visited[j]) {
            cnt++;
            dfs(j, depth+1);
            low[u] = min(low[u], low[j]);
            if (u!=root && low[j]>=dfn[u])
                f[u]++;
            if (u==root && cnt>=2)
                f[u]++;
        } else low[u] = min(low[u], dfn[j]);
    }
}

        ans = cc = 0;  //cc是连通块的个数，ans是割点的个数
        for (int i=1; i<=n; i++)
            if (!vis[i]) {
                dfs(i, 1, i);
                cc++;
            }
        for (int i=1; i<=n; i++)
            if (f[i] >= 1)
                ans++;
        printf("%d %d\n", ans, cc);

Tarjan算法求解桥和边双连通分量

对于边双连通分量，我们需要先了解一些概念：

边连通度：使一个子图不连通所需要删除的最小的边数就是该图的边连通度。

桥（割边）：当删除一条边就使得图不连通的那条边称为桥或者是割边。

边双连通分量：边连通度大于等于二的子图称为边双连通分量。

/*
 *无向图的桥及边的双连通分量，Tarjan算法O(E)
 */
#include <cstdio>
#include <cstring>
using namespace std;
#define MAXN 10000
#define MAXM 1000000

struct node {
    int v, w, pre;
} edge[MAXM];
int pos[MAXN], nEdge; //图的存储：链式前向星（池子法）

struct Bridge {
    int u, v;
} bridge[MAXM];  //用来记录桥
int tot; //桥的个数

int fa[MAXN], cc; //fa：各个点所属的缩点（连通块），cc连通块的个数
int dfn[MAXN], low[MAXN], time; //时间戳
int stack[MAXN], top;   //用于维护连通块的
int n, m;   //点的个数和边的条数

void connect(int u, int v, int w) {
    nEdge++;
    edge[nEdge].pre = pos[u];
    edge[nEdge].v = v;
    edge[nEdge].w = w;
    pos[u] = nEdge;
}

void tarjan(int cur, int from) {
    low[cur] = dfn[cur] = time++;
    stack[++top] = cur;
    for (int p=pos[cur]; p; p=edge[p].pre) {
        int v = edge[p].v;
        if (v == from) continue;  //注意一下这里
        if (!dfn[v]) {
            tarjan(v, cur);
            if (low[v] < low[cur]) low[cur] = low[v];
            if (low[v] > dfn[cur]) {
                bridge[tot].u = cur;
                bridge[tot++].v = v;
                cc++;
                do {
                    fa[stack[top]] = cc;
                } while (stack[top--] != v);
            }
        } else if (low[cur] > dfn[v]) low[cur] = dfn[v];
    }
}
int main() {
    scanf("%d%d", &n, &m);

    memset(pos, 0, sizeof(pos));
    nEdge = 0;
    int u, v, w;
    for (int i=0; i<m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        connect(u, v, w);
        connect(v, u, w);
    }

    memset(dfn, 0, sizeof(dfn));
    memset(fa, -1, sizeof(fa));

    cc = tot = 0;
    for (int i=1; i<=n; i++)   //可以处理不连通的无向图，如果连通只需要一次即可
        if (!dfn[i]) {
            top = time = 1;
            tarjan(i, -1);
            ++cc;
            for (int j=1; j<=n; j++)   //特殊处理顶点的连通块
                if (dfn[j] && fa[j]==-1) fa[j] = cc;
        }

    for (int i=1; i<=n; i++)
        printf("%d ", fa[i]);  //输出每个节点所属于的连通块（缩点标号）
    printf("\n");

    for (int i=0; i<tot; i++)
        printf("%d %d\n", bridge[i].u, bridge[i].v); //输出所有的桥

    return 0;
}

无向图割点（割顶）、桥（边的双接通分量+缩点）

相关推荐