锐客网

  1. 首页 > it技术 > >

求桥，边双连通缩点

图论

一个无向图，问最少添加多少条边使任意两点有两条不同路径。
即构造一个边双连通图，边双连通缩点后是一棵树，度数为1的点为a，结论是需要添加(a+1)/2条边。
【求桥，边双连通缩点】

#include #include #include #include #include #include #include #include #include #include #define ll long long #define ull unsigned long long #define debug puts("======"); #define inf (1<<30) #define eps 1e-8 using namespace std; const int MAXN=6005; const int MAXE=20005; struct Edge { int u, v; int next; } edge[MAXE]; int head[MAXN], tot; int n,m; int dfn[MAXN],low[MAXN]; bool vis_e[MAXE]; //是否访问了边 bool is_bridge[MAXE]; //是否是桥 int dfs_clock; int Block[MAXN]; //点所属边双 int block; //边双数 vectorvec[MAXN]; //缩点后图 bool vis[MAXN]; void init(int n) { memset(head, -1, sizeof(head[0])*(n+1)); tot = 0; } void addEdge(int u, int v) { edge[tot].u = u; edge[tot].v = v; edge[tot].next = head[u]; head[u] = tot++; } void dfs(int cur) { dfn[cur] = low[cur] = ++dfs_clock; for(int i = head[cur]; i!=-1; i = edge[i].next) { int tv = edge[i].v; if(!dfn[tv]) { vis_e[i] = vis_e[i^1] = true; //标记边可以处理重边 dfs(tv); low[cur] = min(low[cur], low[tv]); if(dfn[cur] < low[tv]) is_bridge[i] = is_bridge[i^1] = true; } else if(dfn[tv] < dfn[cur] && !vis_e[i]) { vis_e[i] = vis_e[i^1] = true; low[cur] = min(low[cur], dfn[tv]); } } } void find_bridge(int n) { dfs_clock = 0; memset(dfn, 0, sizeof(dfn[0])*(n+1)); memset(vis_e, 0, sizeof(vis_e[0])*tot); memset(is_bridge, 0, sizeof(is_bridge[0])*tot); for(int i = 1; i <= n; ++i) if(!dfn[i]) dfs(i); } void DFS(int u) { vis[u]=1; Block[u]=block; for(int i = head[u]; i!=-1; i = edge[i].next) { int v=edge[i].v; if(vis[v]||is_bridge[i]) continue; DFS(v); } } //不经过桥的情况下，dfs求出每个变双 void find_scc() { memset(vis,0,sizeof(vis)); block=0; for(int i=1; i<=n; i++) { if(!vis[i]) { ++block; vec[i].clear(); DFS(i); } } int deg[MAXN]; memset(deg,0,sizeof(deg)); for(int i=0; i



    推荐阅读


    上一篇：Cohen-Sutherland线段裁剪算法

    下一篇：小技巧|通过AlarmManager+Service+广播实现定时任务。并解决8.0之后service无法启动的问题