HDU - 4612 Warm up
题意：给你一个连通的无向图，问你加一条边后，最少的桥是多少个。
求桥不用说了，板子，然后是加了一条边之后的最少的桥，那其实就是我们求出边双连通分量，
然后缩点，重新建出一棵树，再找出树的直径减去就可以了，需要注意的是，可能会有重边。
1 #include<cstdio> 2 #include<queue> 3 #include<vector> 4 #include<algorithm> 5 using namespace std; 6 const int N=2e5+11,M=1e6+11; 7 struct Side{ 8 int id,v,ne; 9 Side(){} 10 Side(int v,int ne):v(v),ne(ne){} 11 }S[M<<1]; 12 bool vis[N],isq[M]; 13 int n,m,ans,sn,dn,head[N],dfn[N],low[N]; 14 int bn,fp[N],bin[N]; 15 vector<int> vv[N]; 16 void init(){ 17 sn=dn=bn=0; 18 for(int i=0;i<=n;i++){ 19 dfn[i]=bin[i]=0; 20 fp[i]=head[i]=-1; 21 } 22 for(int i=0;i<m;i++) isq[i]=false; 23 } 24 void add(int u,int v,int id){ 25 S[sn].id=id; 26 S[sn].v=v; 27 S[sn].ne=head[u]; 28 head[u]=sn++; 29 } 30 void findq(int u){ 31 dfn[u]=low[u]=++dn; 32 int v,id; 33 for(int i=head[u],v;~i;i=S[i].ne){ 34 v=S[i].v;id=S[i].id; 35 if(!dfn[v]){ 36 fp[v]=id; 37 findq(v); 38 low[u]=min(low[u],low[v]); 39 }else if(id!=fp[u]) low[u]=min(low[u],dfn[v]); 40 } 41 if(fp[u]!=-1&&dfn[u]==low[u]) ans++,isq[fp[u]]=true; 42 } 43 void dfs(int u){ 44 bin[u]=bn; 45 for(int i=head[u];~i;i=S[i].ne){ 46 if(isq[S[i].id]) continue; 47 if(!bin[S[i].v]) dfs(S[i].v); 48 } 49 } 50 int bfs(int beg,int& len){ 51 for(int i=1;i<=bn;i++) vis[i]=false; 52 int dep=0,pos=beg; 53 Side qt; 54 queue<Side> q; 55 vis[beg]=true; 56 q.push(Side(beg,0)); 57 while(!q.empty()){ 58 qt=q.front(); 59 q.pop(); 60 if(qt.ne>dep) dep=qt.ne,pos=qt.v; 61 for(int i=0,v;i<(int)vv[qt.v].size();i++){ 62 v=vv[qt.v][i]; 63 if(!vis[v]){ 64 vis[v]=true; 65 q.push(Side(v,qt.ne+1)); 66 } 67 } 68 } 69 len=dep; 70 return pos; 71 } 72 int solve(){ 73 ans=0; 74 for(int i=1;i<=n;i++) if(!dfn[i]) findq(i); 75 for(int i=1;i<=n;i++) if(!bin[i]) bn++,dfs(i); 76 for(int i=1;i<=bn;i++) vv[i].clear(); 77 //printf("%d\n",bn); 78 int bi,bj,u,len; 79 for(int i=1;i<=n;i++){ 80 // printf("%d ",bin[i]); 81 bi=bin[i]; 82 for(int j=head[i];~j;j=S[j].ne){ 83 bj=bin[S[j].v]; 84 if(bi!=bj) vv[bi].push_back(bj); 85 } 86 } 87 u=bfs(1,len); 88 // printf("\n%d %d\n",u,len); 89 bfs(u,len); 90 // printf("%d %d\n",ans,len); 91 return ans-len; 92 } 93 int main(){ 94 int u,v; 95 while(~scanf("%d%d",&n,&m)&&(n||m)){ 96 init(); 97 for(int i=0;i<m;i++){ 98 scanf("%d%d",&u,&v); 99 add(u,v,i); 100 add(v,u,i); 101 } 102 printf("%d\n",solve()); 103 } 104 return 0; 105 }