首页 > 代码库 > POJ 3177 边双连通求连通量度的问题
POJ 3177 边双连通求连通量度的问题
这道题的总体思路就是找到连通量让它能够看作一个集合，然后找这个集合的度，度数为1的连通量为k，那么需要添加（k+1）/2条边才可以保证边双连通
这里因为一个连通量中low[]大小是相同的，所以我们用ans[low[i]]++来计度数
这道题我最开始按学长的模板来写。。。。MLE到哭了，也不知道这道题为什么这么逗，把5000的数组改成1000也能过，当然后来换了别的思路
为了防止重边的进入，开始设置了一个hash[][]二维数组来判断边是否已经存在，不额外添入
之后，我不采用二维数组，而是在get_bcc函数中利用visit[]一维数组来防止重边的多次访问，也就是说我允许添入多个边，但我不让它多次被访问
这样每循环一次，我就需要更新一次数组，但是空间耗费少了特别多还是很好的。
自己修改多次的代码：
#include <cstdio>#include <cstring>#include <vector>#include <algorithm>using namespace std;#define N 5005int k,n,first[N],tmpdfn,dfn[N],low[N],cnt;//isBridge[][]用来判断是否为桥,cnt记载桥的个数struct Path{ int y,next;}path[2*N];void add(int x,int y){ path[k].y=y,path[k].next=first[x]; first[x]=k; k++;}void dfs(int u,int fa){ dfn[u]=low[u]=++tmpdfn; for(int i=first[u];i!=-1;i=path[i].next){ int v=path[i].y; if(!dfn[v]){ dfs(v,u); low[u]=min(low[u],low[v]); } else if(v!=fa) low[u]=min(low[u],dfn[v]); }}void get_bcc(int n){ int visit[N]; cnt=0; int ans[N]; memset(ans,0,sizeof(ans)); for(int i=1;i<=n;i++){ if(!dfn[i]) dfs(n,-1); } for(int i=1;i<=n;i++){ memset(visit,0,sizeof(visit)); for(int j=first[i];j!=-1;j=path[j].next){ int v=path[j].y; if(low[i]!=low[v]&&!visit[v]) ans[low[i]]++,visit[v]=1; } } for(int i=1;i<=n;i++) if(ans[i]==1) cnt++;}int main(){ int R,x,y; while(scanf("%d%d",&n,&R)!=EOF){ tmpdfn=0,k=0; memset(dfn,0,sizeof(dfn)); memset(first,-1,sizeof(first)); for(int i=0;i<R;i++){ scanf("%d%d",&x,&y); add(x,y); add(y,x); } get_bcc(n); printf("%d\n",(cnt+1)/2); } return 0;}
学长的代码，作为模版还是很有价值的：
#include <iostream>#include <cstdio>#include <cstring>#include <vector>#define maxn 1010using namespace std;int pre[maxn],dfs_clock,isbridge[maxn][maxn];vector<int> G[maxn];bool hash[maxn][maxn];int dfs1(int u,int fa){ int lowu = pre[u] = ++dfs_clock; for(int i = 0;i < G[u].size();i++){ int v = G[u][i]; if(!pre[v]){ int lowv = dfs1(v,u); lowu = min(lowu,lowv); if(lowv > pre[u]){ isbridge[u][v] = isbridge[v][u] = 1; } }else if(pre[v] < pre[u] && v != fa){ lowu = min(lowu,pre[v]); } } return lowu;}int fa[maxn],vis[maxn];int find(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);}void dfs2(int u){ for(int i = 0;i < G[u].size();i++){ int v = G[u][i]; if(!vis[v] && !isbridge[u][v]){ int x = find(u);int y = find(v); if(x != y) fa[x] = y; vis[v] = 1; dfs2(v); } }}void find_bcc(int n){ memset(pre,0,sizeof(pre)); memset(isbridge,0,sizeof(isbridge)); dfs_clock = 0; for(int i = 0;i < n;i++) if(!pre[i]) dfs1(i,-1); for(int i = 0;i < n;i++){ if(!vis[i]){ vis[i] = 1; dfs2(i); } }}int degree[maxn];bool used[maxn];int main(){ int n,m; while(scanf("%d%d",&n,&m) == 2){ for(int i = 0;i < n;i++){ fa[i] = i; G[i].clear(); } memset(hash,0,sizeof(hash)); for(int i = 0;i < m;i++){ int a,b; scanf("%d%d",&a,&b); a--;b--; if(!hash[a][b]){ G[a].push_back(b); G[b].push_back(a); hash[a][b] = hash[b][a] = 1; } } find_bcc(n); memset(degree,0,sizeof(degree)); memset(used,0,sizeof(used)); for(int i = 0;i < n;i++) for(int j = 0;j < G[i].size();j++){ if(find(i) != find(G[i][j])) degree[find(G[i][j])]++; } int sum = 0; for(int i = 0;i < n;i++){ int x = find(i); if(!used[x]){ used[x] = 1; if(degree[x] == 1) sum++; else if(degree[x] == 0) sum += 2; } } int cnt = 0; for(int i = 0;i < n;i++){ if(used[i] == 1) cnt++; } if(cnt == 1) printf("0\n"); else printf("%d\n",(sum+1)/2); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。