POJ 3694 Network
题目大意:
给一个连通图G,问加入某一条边后图中还有多少割边。
解题思路:
1、用Tarjan算法求出所有的割边和每一个点的父节点,并记录。记录每一个节点的父节点可以形成一棵深搜树。
2、通过求LCA(最近公共祖先)的过程中对于深搜树的处理,记录经过的割边的数量并减去。
注意事项:
1、因为数据比较大,所以每加一次边用Tarjan求一次割边数量是不现实的,并且是不符合题意的。因为某两个点之间原来有一条边,现在再加一条。这样的情况他俩之间就没有割边了。
2、当DFN[U]<LOW[V]时,说明边(U,V)是一条割边。
3、求LCA是没有模板的,但是有一点必须要办的是就要生成一棵树。这样才能求LCA。
下面是代码:
#include <stdio.h> #include <string.h> const int MAXN=100005; struct node { int to,next; } edge[MAXN*4]; int head[MAXN],dfn[MAXN],low[MAXN],pre[MAXN],vis[MAXN],n,m,time,cnt,cut; bool bi[MAXN]; void init() { memset(vis,0,sizeof(vis)); memset(head,-1,sizeof(head)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); for(int i=0; i<=n; pre[i]=i,i++); memset(bi,0,sizeof(bi)); cnt=0; cut=0; time=1; } int min(int a,int b) { if(a>b)a=b; return a; } void addedge(int u,int v) { edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt; cnt++; } void dfs(int u,int fa) { dfn[u]=time; low[u]=time; time++; vis[u]=1; for(int i=head[u]; i!=-1; i=edge[i].next) { int v=edge[i].to; if(!vis[v]) { dfs(v,u); pre[v]=u; //记录父节点 low[u]=min(low[u],low[v]); if(low[v] > dfn[u]) //如果子节点的low值大于父节点的时间戳这就是桥 { cut++; bi[v] = true; } } else if(vis[v] == 1 && v != fa) { low[u]=min(low[u],dfn[v]); } } vis[u]=2; } int judge(int u,int v) { int cnt1=0; while(dfn[u]>dfn[v]) { if(bi[u]) { cnt1++; bi[u]=false; } u=pre[u]; } while(dfn[u]<dfn[v]) { if(bi[v]) { cnt1++; bi[v]=false; } v=pre[v]; } while(u!=v) { if(bi[u]) { bi[u]=false; cnt1++; } if(bi[v]) { bi[v]=false; cnt1++; } u=pre[u]; v=pre[v]; } return cnt1; } int main() { int u,v,q,in=0; while(scanf("%d%d",&n,&m),n+m) { if(in) { puts(""); } in++; init(); for(int i=0; i<m; i++) { scanf("%d%d",&u,&v); u--; v--; addedge(u,v); //?T?òí??ó???ò±? addedge(v,u); } dfs(0,0); scanf("%d",&q); printf("Case %d:\n",in); for(int i=0; i<q; i++) { scanf("%d%d",&u,&v); u--; v--; cut-=judge(u,v); printf("%d\n",cut); } } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。