【PTA数据结构 | C语言版】双连通分量

本专栏持续输出数据结构题目集，欢迎订阅。

题目

本题请你编写程序，输出给定无向连通图中的割点和割边。

输入格式：
输入首先在第一行给出图中最大顶点数量，即正整数 kMaxVertex（≤20）。
第二行给出两个正整数，依次为当前要创建的图的顶点数 n 和边数 m（保证顶点数至少为 2 且不超过最大顶点数量）。
第三行给出 n 个小写英文字母，其间以 1 个空格分隔，顺序对应每个顶点的信息。
随后 m 行，每行给出一条无向边的两个端点的编号。顶点编号从 0 开始，编号间以 1 个空格分隔。
题目保证没有边被重复给出，并且图一定是连通的。

输出格式：
首先在一行中输出所有割点的字母信息，中间不要空格。如果没有割点则输出一个空行。
随后每行按格式 (v1, v2) 输出一条割边，其中 v1 和 v2 为割边两端点的字母信息。如果没有割边则不要输出任何信息。

输入样例：
20
10 11
a b c d e f g h i j
0 1
1 2
1 3
2 4
3 4
3 5
5 6
5 7
6 7
7 8
7 9

输出样例：
bdfh
(b, a)
(d, f)
(h, i)
(h, j)

注意：割点和割边的输出顺序是不唯一的，以任何顺序输出都可以，有特殊裁判程序判断输出的正确性。例如下列输出也是正确的。

hbdf
(d, f)
(h, i)
(a, b)
(h, j)

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_VERTEX 20typedef struct Node {int vertex;struct Node* next;
} Node;typedef struct {Node* adj[MAX_VERTEX];int n;char vertices[MAX_VERTEX];
} Graph;// 全局变量
int time;
int disc[MAX_VERTEX];    // 发现时间
int low[MAX_VERTEX];     // 最早可达祖先的发现时间
int parent[MAX_VERTEX];  // 父节点
int ap[MAX_VERTEX];      // 标记割点
int bridges[MAX_VERTEX][MAX_VERTEX]; // 标记割边// 函数声明
void initGraph(Graph* g, int n);
void addEdge(Graph* g, int src, int dest);
void findAPAndBridges(Graph* g);
void APUtil(Graph* g, int u);
void printResults(Graph* g);int main() {int kMaxVertex;(void)scanf("%d", &kMaxVertex);int n, m;(void)scanf("%d %d", &n, &m);Graph g;initGraph(&g, n);// 读取顶点信息for (int i = 0; i < n; i++) {(void)scanf(" %c", &g.vertices[i]);}// 读取边信息for (int i = 0; i < m; i++) {int src, dest;(void)scanf("%d %d", &src, &dest);addEdge(&g, src, dest);}// 初始化time = 0;for (int i = 0; i < n; i++) {disc[i] = -1;low[i] = -1;parent[i] = -1;ap[i] = 0;for (int j = 0; j < n; j++) {bridges[i][j] = 0;}}// 查找割点和割边findAPAndBridges(&g);// 输出结果printResults(&g);return 0;
}// 初始化图
void initGraph(Graph* g, int n) {g->n = n;for (int i = 0; i < n; i++) {g->adj[i] = NULL;}
}// 添加无向边
void addEdge(Graph* g, int src, int dest) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->vertex = dest;newNode->next = g->adj[src];g->adj[src] = newNode;newNode = (Node*)malloc(sizeof(Node));newNode->vertex = src;newNode->next = g->adj[dest];g->adj[dest] = newNode;
}// 查找割点和割边
void findAPAndBridges(Graph* g) {// 对每个未访问的顶点调用APUtilfor (int i = 0; i < g->n; i++) {if (disc[i] == -1) {APUtil(g, i);}}
}// Tarjan算法核心函数
void APUtil(Graph* g, int u) {int children = 0;disc[u] = low[u] = ++time;Node* temp = g->adj[u];while (temp != NULL) {int v = temp->vertex;if (disc[v] == -1) {children++;parent[v] = u;APUtil(g, v);// 更新low值low[u] = (low[u] < low[v]) ? low[u] : low[v];// 检查是否为割点if (parent[u] == -1 && children > 1) {ap[u] = 1;}if (parent[u] != -1 && low[v] >= disc[u]) {ap[u] = 1;}// 检查是否为割边if (low[v] > disc[u]) {bridges[u][v] = bridges[v][u] = 1;}} else if (v != parent[u]) {// 更新low值为发现时间较小值low[u] = (low[u] < disc[v]) ? low[u] : disc[v];}temp = temp->next;}
}// 输出结果
void printResults(Graph* g) {// 输出割点for (int i = 0; i < g->n; i++) {  // 移除未使用的hasAP变量if (ap[i]) {printf("%c", g->vertices[i]);  // 使用->访问指针成员}}printf("\n");// 输出割边for (int i = 0; i < g->n; i++) {for (int j = i + 1; j < g->n; j++) {if (bridges[i][j]) {// 使用->访问指针成员printf("(%c, %c)\n", g->vertices[i], g->vertices[j]);}}}
}