网页资讯视频图片知道文库贴吧地图采购
进入贴吧全吧搜索

 
 
 
日一二三四五六
       
       
       
       
       
       

签到排名:今日本吧第个签到,

本吧因你更精彩,明天继续来努力!

本吧签到人数:0

一键签到
成为超级会员,使用一键签到
一键签到
本月漏签0次!
0
成为超级会员,赠送8张补签卡
如何使用?
点击日历上漏签日期,即可进行补签。
连续签到:天  累计签到:天
0
超级会员单次开通12个月以上,赠送连续签到卡3张
使用连续签到卡
08月29日漏签0天
c语言吧 关注:799,038贴子:4,359,600
  • 看贴

  • 图片

  • 吧主推荐

  • 视频

  • 游戏

  • 1回复贴,共1页
<<返回c语言吧
>0< 加载中...

求助萌新求教,这道题代码怎么写啊

  • 只看楼主
  • 收藏

  • 回复
  • 蓝雨青烟
  • 毛蛋
    1
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
题目:给定连通无向图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;
}
怎么改啊


  • Flandrekjhhjki
  • 毛蛋
    1
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
谁教的在edge_cnt初始化为0的情况下拿i和i^1遍历无向图的
要么改成1要么老老实实用i+1
tarjan没看出来问题,不过有些没用的操作是真的
随手捏了几个数据验了下没啥问题,把上面那点改了就行了
main里面edge_cnt+=2和所有memset全部没用,建议删了
tarjan里面的child_count也没啥用


登录百度账号

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频!
  • 贴吧页面意见反馈
  • 违规贴吧举报反馈通道
  • 贴吧违规信息处理公示
  • 1回复贴,共1页
<<返回c语言吧
分享到:
©2025 Baidu贴吧协议|隐私政策|吧主制度|意见反馈|网络谣言警示