无向图的双连通分量c语言

以下是无向图的双连通分量的 C 语言代码实现，基于 Tarjan 算法：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 1000

int n, m, top, cnt, bcnt;
int head[MAXN + 1], dfn[MAXN + 1], low[MAXN + 1], stack[MAXN + 1], belong[MAXN + 1];
struct Edge {
    int to, next;
} edge[MAXN * 2 + 1];

void addEdge(int u, int v) {
    edge[++cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++cnt;
    stack[++top] = u;
    int flag = 0;
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (!dfn[v]) {
            tarjan(v, u);
            low[u] = low[u] < low[v] ? low[u] : low[v];
            if (dfn[u] <= low[v]) {
                flag++;
                if (fa || flag > 1) {
                    belong[u] = ++bcnt;
                    while (stack[top] != u) {
                        belong[stack[top]] = bcnt;
                        top--;
                    }
                }
                else if (fa == 0 && flag == 1) {
                    belong[u] = ++bcnt;
                    belong[stack[top]] = bcnt;
                    top--;
                }
            }
        }
        else if (v != fa && dfn[v] < dfn[u]) {
            low[u] = low[u] < dfn[v] ? low[u] : dfn[v];
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        addEdge(u, v);
        addEdge(v, u);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            tarjan(i, 0);
            if (top) {
                bcnt++;
                while (top) {
                    belong[stack[top]] = bcnt;
                    top--;
                }
            }
        }
    }
    printf("There are %d biconnected components in the graph.\n", bcnt);
    for (int i = 1; i <= n; i++) {
        printf("The vertex %d belongs to the %d-th biconnected component.\n", i, belong[i]);
    }
    return 0;
}

其中，`n` 和 `m` 分别表示无向图的顶点数和边数，`head[]` 数组存储邻接表，`dfn[]` 和 `low[]` 分别表示 DFS 序和能够回溯到的最小祖先，`stack[]` 用于存储访问过的节点，`belong[]` 存储每个节点所属的双连通分量编号，`cnt` 用于记录边数，`top` 表示栈顶，`bcnt` 表示双连通分量的数量。

Tarjan 算法的具体实现见代码中的 `tarjan()` 函数。在程序最后，输出了双连通分量的数量和每个节点所属的双连通分量编号。