大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
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.net/116888.html原文链接：https://javaforall.net
