蓝雨青烟 而猪头
关注数: 21 粉丝数: 31 发帖数: 216 关注贴吧数: 14
萌新求教,这道题代码怎么写啊 题目:给定连通无向图G中的一条边,如果删除它G就不连通,那么称这条边为桥。修改寻找关节点的算法,使他能探测桥. #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXN 1005 #define MAXM 10005 struct edge { int to, next; bool is_bridge; } edges[MAXM * 2]; int head[MAXN], edge_cnt = 0; int dfn[MAXN], low[MAXN], timestamp = 1; void add_edge(int u, int v) { ++edge_cnt; edges[edge_cnt].to = v; edges[edge_cnt].next = head[u]; head[u] = edge_cnt; } // dfs(t, s) 表示深度优先遍历以 t 为根的子树(t 的父节点是 s) void tarjan(int t, int s) { dfn[t] = low[t] = timestamp++; int child_cnt = 0; for (int i = head[t]; i; i = edges[i].next) { int v = edges[i].to; if (!dfn[v]) { // v 没有访问过,是 t 的子节点 ++child_cnt; tarjan(v, t); low[t] = low[t] < low[v] ? low[t] : low[v]; if (low[v] > dfn[t]) { edges[i].is_bridge = edges[i ^ 1].is_bridge = true; // 记录桥 } } else if (v != s) { // v 已经访问过了且不是 t 的父节点,更新 low 值 low[t] = low[t] < dfn[v] ? low[t] : dfn[v]; } } if (t == s && child_cnt > 1 || t != s && edges[t << 1].is_bridge) { edges[t << 1].is_bridge = edges[(t << 1) + 1].is_bridge = true; // 更新父边是桥的情况 } } int main() { int n, m; scanf("%d%d", &n, &m); memset(head, 0, sizeof(head)); memset(edges, 0, sizeof(edges)); // 修改这里 while (m--) { int u, v; scanf("%d%d", &u, &v); add_edge(u, v); add_edge(v, u); edge_cnt += 2; // 修改这里 } memset(dfn, 0, sizeof(dfn)); // 修改这里 timestamp = 1; // 修改这里 for (int i = 1; i <= n; i++) { if (!dfn[i]) { tarjan(i, i); } } printf("Bridge edges:\n"); for (int i = 2; i <= edge_cnt; i += 2) { if (edges[i].is_bridge) { printf("%d - %d\n", edges[i ^ 1].to, edges[i].to); } } return 0; } 怎么改啊
1 下一页