当前位置:网站首页>POJ 3177 Redundant Paths POJ 3352 Road Construction(双连接)
POJ 3177 Redundant Paths POJ 3352 Road Construction(双连接)
2022-07-06 17:56:00 【全栈程序员站长】
大家好,又见面了,我是全栈君
POJ 3177 Redundant Paths
POJ 3352 Road Construction
题意:两题一样的。一份代码能交。给定一个连通无向图,问加几条边能使得图变成一个双连通图
思路:先求双连通。缩点后。计算入度为1的个数,然后(个数 + 1) / 2 就是答案(这题因为是仅仅有一个连通块所以能够这么搞,假设有多个,就不能这样搞了)
代码:
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N = 1005;const int M = 20005;int n, m;struct Edge { int u, v, id; bool iscut; Edge() {} Edge(int u, int v, int id) { this->u = u; this->v = v; this->id = id; this->iscut = false; }} edge[M];int first[N], next[M], en;void add_edge(int u, int v, int id) { edge[en] = Edge(u, v, id); next[en] = first[u]; first[u] = en++;}void init() { en = 0; memset(first, -1, sizeof(first));}int pre[N], dfn[N], dfs_clock, bccno[N], bccn;void dfs_cut(int u, int id) { pre[u] = dfn[u] = ++dfs_clock; for (int i = first[u]; i + 1; i = next[i]) { if (edge[i].id == id) continue; int v = edge[i].v; if (!pre[v]) { dfs_cut(v, edge[i].id); dfn[u] = min(dfn[u], dfn[v]); if (dfn[v] > pre[u]) edge[i].iscut = edge[i^1].iscut = true; } else dfn[u] = min(dfn[u], pre[v]); }}void find_cut() { dfs_clock = 0; memset(pre, 0, sizeof(pre)); for (int i = 1; i <= n; i++) if (!pre[i]) dfs_cut(i, -1);}void dfs_bcc(int u) { bccno[u] = bccn; for (int i = first[u]; i + 1; i = next[i]) { if (edge[i].iscut) continue; int v = edge[i].v; if (bccno[v]) continue; dfs_bcc(v); }}void find_bcc() { bccn = 0; memset(bccno, 0, sizeof(bccno)); for (int i = 1; i <= n; i++) { if (!bccno[i]) { bccn++; dfs_bcc(i); } }}int du[N];int main() { while (~scanf("%d%d", &n, &m)) { int u, v; init(); for (int i = 0; i < m; i++) { scanf("%d%d", &u, &v); add_edge(u, v, i); add_edge(v, u, i); } find_cut(); find_bcc(); memset(du, 0, sizeof(du)); for (int i = 0; i < en; i += 2) { if (!edge[i].iscut) continue; int u = bccno[edge[i].u], v = bccno[edge[i].v]; if (u == v) continue; du[u]++; du[v]++; } int cnt = 0; for (int i = 1; i <= bccn; i++) if (du[i] == 1) cnt++; printf("%d\n", (cnt + 1) / 2); } return 0;}
版权声明:本文博主原创文章,博客,未经同意不得转载。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116888.html原文链接:https://javaforall.cn
边栏推荐
猜你喜欢
HMM 笔记
Transformation transformation operator
2022 Google CTF segfault Labyrinth WP
Data type of pytorch tensor
1123. 最深叶节点的最近公共祖先
Body mass index program, entry to write dead applet project
Go zero micro service practical series (IX. ultimate optimization of seckill performance)
黑马笔记---创建不可变集合与Stream流
身体质量指数程序,入门写死的小程序项目
go-zero微服务实战系列(九、极致优化秒杀性能)
随机推荐
Vocabulary in Data Book
Taro applet enables wxml code compression
树莓派/arm设备上安装火狐Firefox浏览器
实现mysql与ES的增量数据同步
Failed to successfully launch or connect to a child MSBuild. exe process. Verify that the MSBuild. exe
【信号与系统】
1123. The nearest common ancestor of the deepest leaf node
【案例分享】网络环路检测基本功能配置
ClickHouse字段分组聚合、按照任意时间段粒度查询SQL
Wood extraction in Halcon
Installation of gazebo & connection with ROS
Spark TPCDS Data Gen
Transplant DAC chip mcp4725 to nuc980
阿里云中mysql数据库被攻击了,最终数据找回来了
[chip scheme design] pulse oximeter
Your cache folder contains root-owned files, due to a bug in npm ERR! previous versions of npm which
The difference between spin and sleep
C# 计算农历日期方法 2022
THREE.AxesHelper is not a constructor
从底层结构开始学习FPGA----FIFO IP的定制与测试