本题的意思是给你一个图，再依次的加边问你还有几条桥
[构造双连通图]
一个有桥的连通图，如何把它通过加边变成边双连通图？方法为首先求出所有的桥，然后删除这些桥边，剩下的每个连通块都是一个双连通子图。把每个双连通子图收缩为一个顶点，再把桥边加回来，最后的这个图一定是一棵树，边连通度为1。
统计出树中度为1的节点的个数，即为叶节点的个数，记为leaf。则至少在树上添加(leaf+1)/2条边，就能使树达到边二连通，所以至少添加的边数就是(leaf+1)/2。具体方法为，首先把两个最近公共祖先最远的两个叶节点之间连接一条边，这样可以把这两个点到祖先的路径上所有点收缩到一起，因为一个形成的环一定是双连通的。然后再找两个最近公共祖先最远的两个叶节点，这样一对一对找完，恰好是(leaf+1)/2次，把所有点收缩到了一起。
本题的意思和这差不多
#include<iostream> #include<algorithm> using namespace std; const int N=100009; struct node { int v,next; } point[N*4]; int dfn[N],low[N],head[N],Dfn[N],father[N]; int n,num,tot,index; bool qiao[N];//标记桥边 void init() { for(int i=0;i<=n;i++) { dfn[i]=0; Dfn[i]=0; head[i]=-1; father[i]=0; qiao[i]=0; } tot=num=index=0; } int min(int a,int b) { if(a<b)return a; else return b; } void add(int a,int b)//因为无向图所以是双向的 { point[tot].v=b; point[tot].next=head[a]; head[a]=tot++; point[tot].v=a; point[tot].next=head[b]; head[b]=tot++; } void tarjan(int u,int fa) { dfn[u]=low[u]=++index; Dfn[u]=Dfn[fa]+1;//节点的深度 int flag=1; for(int i=head[u];i+1;i=point[i].next) { int v=point[i].v; if(v==fa&&flag)//重边 { flag=0; continue; } if(!dfn[v]) { father[v]=u; tarjan(v,u); low[u]=min(low[u],low[v]); if(dfn[u]<low[v])//这个就是判断桥的条件 { num++; qiao[v]=1; } }else low[u]=min(low[u],dfn[v]); } } void lca(int u,int v) { while(Dfn[v]>Dfn[u])//让它们达到统一高度 { if(qiao[v]) { num--; qiao[v]=0; } v=father[v]; } while(Dfn[u]>Dfn[v]) { if(qiao[u]) { num--; qiao[u]=0; } u=father[u]; } while(v!=u) { if(qiao[v]) { num--; qiao[v]=0; } if(qiao[u]) { num--; qiao[u]=0; } v=father[v]; u=father[u]; } } int main() { int i,a,b,m; int cas=1,t; while(scanf("%d%d",&n,&m),n+m) { init(); for(i=0; i<m; i++) { scanf("%d%d",&a,&b); add(a,b); } tarjan(1,0); scanf("%d",&t); printf("Case %d: ",cas++); while(t--) { scanf("%d%d",&a,&b); lca(a,b); printf("%d ",num); } } return 0; }
昨天学习了LCA今天就做这个经典的LCA吧，刚开始一直TLE，开始在lca函数中用的是swap（u,v）超时，我无解了，后来就直接两个while循环了，就AC了，感觉有点坑