首页 > 代码库 > POJ3352-Road Construction(边连通分量)
POJ3352-Road Construction(边连通分量)
题目链接
题意:问要添加几条边才能使所给无向图图变成边双连通图。
思路:一个有桥的连通图,如何把它通过加边变成边双连通图?方法为首先求出所有的桥,然后删除这些桥边,剩下的每个连通块都是一个双连通子图。把每个双连通子图收缩为一个顶点,再把桥边加回来,最后的这个图一定是一棵树,边连通度为1。
统计出树中度为1的节点的个数,即为叶节点的个数,记为leaf。则至少在树上添加(leaf+1)/2条边,就能使树达到边二连通,所以至少添加的边数就是(leaf+1)/2。具体方法为,首先把两个最近公共祖先最远的两个叶节点之间连接一条边,这样可以把这两个点到祖先的路径上所有点收缩到一起,因为一个形成的环一定是双连通的。然后再找两个最近公共祖先最远的两个叶节点,这样一对一对找完,恰好是(leaf+1)/2次,把所有点收缩到了一起。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int MAXN = 5005; vector<int> g[MAXN]; int pre[MAXN], low[MAXN], dg[MAXN], dfs_clock; bool vis[MAXN], map[MAXN][MAXN]; int n, r; void tarjan(int u, int fa) { pre[u] = low[u] = ++dfs_clock; vis[u] = 1; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (v == fa) continue; if (!pre[v]) { tarjan(v, u); low[u] = min(low[u], low[v]); } else if (vis[v]) { low[u] = min(low[u], pre[v]); } } } void find_ebc() { memset(pre, 0, sizeof(pre)); memset(low, 0, sizeof(low)); memset(vis, 0, sizeof(vis)); dfs_clock = 0; for (int i = 1; i <= n; i++) if (!pre[i]) tarjan(i, -1); } int main() { while (scanf("%d%d", &n, &r) != EOF) { for (int i = 1; i <= n; i++) g[i].clear(); memset(map, 0, sizeof(map)); int u, v; for (int i = 0; i < r; i++) { scanf("%d%d", &u, &v); if (!map[u][v]) { g[u].push_back(v); g[v].push_back(u); map[u][v] = map[v][u] = 1; } } find_ebc(); memset(dg, 0, sizeof(dg)); for (int u = 1; u <= n; u++) { for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (low[u] != low[v]) dg[low[u]]++; } } int cnt = 0; for (int i = 1; i <= n; i++) if (dg[i] == 1) cnt++; printf("%d\n", (cnt + 1) / 2); } return 0; }
POJ3352-Road Construction(边连通分量)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。