当前位置:网站首页>POJ 3177 redundant paths POJ 3352 road construction (dual connection)
POJ 3177 redundant paths POJ 3352 road construction (dual connection)
2022-07-07 01:42:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack
POJ 3177 Redundant Paths
POJ 3352 Road Construction
The question : The two questions are the same . A piece of code can hand in . Given a connected undirected graph , How many edges can make a graph become a biconnected graph
Ideas : Find biconnection first . Shrink a little . The calculated penetration is 1 The number of , then ( Number + 1) / 2 That's the answer. ( This problem can be solved because there is only one connected block , Suppose there are more than one , You can't do this )
Code :
#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;}
Copyright notice : This article is the original article of the blogger , Blog , Do not reprint without permission .
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/116888.html Link to the original text :https://javaforall.cn
边栏推荐
- [advanced C language] 8 written questions of pointer
- AcWing 1140. Shortest network (minimum spanning tree)
- 云呐|工单管理软件,工单管理软件APP
- Instructions for using the domain analysis tool bloodhound
- Set up [redis in centos7.x]
- 405 method not allowed appears when the third party jumps to the website
- AcWing 1148. 秘密的牛奶运输 题解(最小生成树)
- 使用nodejs完成判断哪些项目打包+发版
- Start from the bottom structure to learn the customization and testing of fpga---- FIFO IP
- golang 基础 —— 数据类型
猜你喜欢
Baidu flying general BMN timing action positioning framework | data preparation and training guide (Part 1)
How to manage distributed teams?
JS reverse -- ob confusion and accelerated music that poked the [hornet's nest]
Right mouse button customization
Can't you understand the code of linked list in C language? An article allows you to grasp the secondary pointer and deeply understand the various forms of parameter passing in the function parameter
Make Jar, Not War
【C语言进阶篇】指针的8道笔试题
百度飞将BMN时序动作定位框架 | 数据准备与训练指南 (下)
云呐|工单管理办法,如何开展工单管理
刨析《C语言》【进阶】付费知识【完结】
随机推荐
According to the analysis of the Internet industry in 2022, how to choose a suitable position?
Baidu flying general BMN timing action positioning framework | data preparation and training guide (Part 1)
1123. The nearest common ancestor of the deepest leaf node
Taro applet enables wxml code compression
前置机是什么意思?主要作用是什么?与堡垒机有什么区别?
Google released a security update to fix 0 days that have been used in chrome
AcWing 346. 走廊泼水节 题解(推公式、最小生成树)
Docker method to install MySQL
AcWing 346. Solution to the problem of water splashing festival in the corridor (deduction formula, minimum spanning tree)
AcWing 1141. LAN problem solving (kruskalkruskal finding the minimum spanning tree)
[advanced C language] 8 written questions of pointer
js如何快速创建一个长度为 n 的数组
454-百度面经1
JS Es5 can also create constants?
永久的摇篮
Using the entry level of DVA in taro3.*
Spark TPCDS Data Gen
JS ES5也可以创建常量?
Taro2.* applet configuration sharing wechat circle of friends
AI automatically generates annotation documents from code