POJ3177 Redundant Paths (双联通缩点)
求对于给定一个连通图,加多少条边可以变成边双连通图。
一个有桥的连通图要变成边双连通图的话,把双连通子图收缩为一个点,形成一颗树。需要加的边为(leaf+1)/2 (leaf为叶子结点个数)。
对于此题,有重边但重边不加入计算。
重边的话,要么在开始去掉,要么用桥来计算入度。
因为桥不属于任何一个边双连通分支,其余的边和每个顶点都属于且只属于一个边双连通分支。对于重边而言,只有一对边被标记为桥,而对于所有重边来言,belong【u】和belong【v】都是不一样的,那么如果用belong【u】!=belong【v】作为添加入度条件的话,毫无疑问会多加的。
这么说的话,缩点重新建图的话,用桥来建更好一点,这样新图就不会有重边。
代码(用桥计算):
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<cstdio> #include<cmath> #include<map> #include<queue> #include<vector> #include<cstring> #include<algorithm> #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rev(i,a,b) for(int i=(a);i>=(b);i--) #define clr(a,x) memset(a,x,sizeof a) #define INF 0x3f3f3f3f typedef long long LL; using namespace std; const int maxn=200005; const int maxm=2000005; struct node { int u,v; bool operator<(const node &b)const { if(b.u!=u)return u<b.u; return v<b.v; } }da[maxm/2]; int first[maxn],ecnt,u[maxm],v[maxm],nex[maxm]; int low[maxn],dfn[maxn],stck[maxn],belong[maxn]; int indx,top,block,bridge; bool ins[maxn],ecut[maxm]; int n,m; int du[maxn]; void tarjan(int s,int pre) { low[s]=dfn[s]=++indx; stck[top++]=s; ins[s]=1; for(int e=first[s];~e;e=nex[e]) { if(v[e]==pre)continue; if(!dfn[v[e]]) { tarjan(v[e],s); low[s]=min(low[s],low[v[e]]); if(low[v[e]]>dfn[s]) { bridge++; ecut[e]=ecut[e^1]=1; } } else if(ins[v[e]])low[s]=min(low[s],dfn[v[e]]); } if(low[s]==dfn[s]) { int v; block++; do { v=stck[--top]; ins[v]=false; belong[v]=block; }while(v!=s); } } void solve(int n) { clr(dfn,0); clr(ins,0); indx=block=top=0; for(int i=1;i<=n;i++) if(!dfn[i])tarjan(1,0); } void add_(int a,int b) { u[ecnt]=a; v[ecnt]=b; ecut[ecnt]=0; nex[ecnt]=first[a]; first[a]=ecnt++; } int main() { int a,b; while(~scanf("%d%d",&n,&m)) { ecnt=0; clr(first,-1); for(int i=0;i<m;i++) { scanf("%d%d",&a,&b); add_(a,b); add_(b,a); } solve(n); clr(du,0); for(int i=0;i<ecnt;i++) if(ecut[i]) { du[belong[u[i]]]++; } int sum=0; for(int i=1;i<=block;i++) if(du[i]==1)sum++; printf("%d\n",(sum+1)/2); } return 0; }
代码二:
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<cstdio> #include<cmath> #include<map> #include<queue> #include<vector> #include<cstring> #include<algorithm> #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rev(i,a,b) for(int i=(a);i>=(b);i--) #define clr(a,x) memset(a,x,sizeof a) #define INF 0x3f3f3f3f typedef long long LL; using namespace std; const int maxn=200005; const int maxm=2000005; struct node { int u,v; bool operator<(const node &b)const { if(b.u!=u)return u<b.u; return v<b.v; } }da[maxm/2]; int first[maxn],ecnt,u[maxm],v[maxm],nex[maxm];bool g[5005][5005]; int low[maxn],dfn[maxn],stck[maxn],belong[maxn]; int indx,top,block,bridge; bool ins[maxn],ecut[maxm]; int n,m; int du[maxn]; void tarjan(int s,int pre) { low[s]=dfn[s]=++indx; stck[top++]=s; ins[s]=1; for(int e=first[s];~e;e=nex[e]) { if(v[e]==pre)continue; if(!dfn[v[e]]) { tarjan(v[e],s); low[s]=min(low[s],low[v[e]]); if(low[v[e]]>dfn[s]) { bridge++; ecut[e]=ecut[e^1]=1; } } else if(ins[v[e]])low[s]=min(low[s],dfn[v[e]]); } if(low[s]==dfn[s]) { int v; block++; do { v=stck[--top]; ins[v]=false; belong[v]=block; }while(v!=s); } } void solve(int n) { clr(dfn,0); clr(ins,0); indx=block=top=0; for(int i=1;i<=n;i++) if(!dfn[i])tarjan(1,0); } void add_(int a,int b) { u[ecnt]=a; v[ecnt]=b; ecut[ecnt]=0; nex[ecnt]=first[a]; first[a]=ecnt++; } int main() { int a,b; while(~scanf("%d%d",&n,&m)) { ecnt=0;clr(g,false); clr(first,-1); for(int i=0;i<m;i++) { scanf("%d%d",&a,&b); if(a!=b&&!g[a][b])g[a][b]=g[b][a]=1,add_(a,b),add_(b,a); } solve(n); clr(du,0); for(int i=0;i<ecnt;i++) if(belong[u[i]]!=belong[v[i]]) { du[belong[u[i]]]++; } int sum=0; for(int i=1;i<=block;i++) if(du[i]==1)sum++; printf("%d\n",(sum+1)/2); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。