问加一条边，最少可以剩下几个桥。
先双连通分量缩点，形成一颗树，然后求树的直径，就是减少的桥。
本题要处理重边的情况。
如果本来就两条重边，不能算是桥。
还会爆栈，只能C++交，手动加栈了
别人都是用的双连通分量，我直接无向图改成有向图搞得强连通水过。
1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include <iostream> 3 #include <vector> 4 #include <queue> 5 #include <string.h> 6 #include <stdlib.h> 7 #include <stdio.h> 8 #include <stack> 9 10 using namespace std; 11 const int maxn = 200005; 12 bool vis[2000005]; 13 struct edge 14 { 15 int v,next; 16 edge() 17 { 18 next = -1; 19 } 20 }edges[maxn*10-45]; 21 struct ed 22 { 23 int u,v; 24 }e[maxn*10-45]; 25 int dfn[200005],low[200005],belong[200005]; 26 bool inst[200005]; 27 int g[maxn]; 28 vector<int>ng[maxn]; 29 30 stack<int>st; 31 int bcnt,cnt,time; 32 33 void init(int n) 34 { 35 int i; 36 for(i =0;i <= n;i++) 37 g[i] = -1; 38 time = 0;bcnt = cnt = 0; 39 return ; 40 } 41 void addedge(int u,int v,int val) 42 { 43 struct edge o; 44 edges[cnt].v = v; 45 edges[cnt].next = g[u]; 46 g[u] = cnt; 47 cnt++; 48 49 return ; 50 } 51 void tarjan(int i) 52 { 53 int j; 54 dfn[i] = low[i] = ++time; 55 inst[i] = 1; 56 st.push(i); 57 58 for(j = g[i];j != -1;j = edges[j].next) 59 { 60 if(vis[j]) continue; 61 vis[j] = vis[j^1] = 1; 62 int v; 63 v = edges[j].v; 64 if(!dfn[v]) 65 { 66 tarjan(v); 67 low[i] = min(low[i],low[v]); 68 } 69 else if(inst[v]) 70 low[i] = min(low[i],dfn[v]); 71 } 72 int k; 73 if(dfn[i] == low[i]) 74 { 75 76 bcnt++; 77 do 78 { 79 k = st.top(); 80 st.pop(); 81 inst[k] = 0; 82 belong[k] = bcnt; 83 84 } 85 while(k != i); 86 } 87 88 } 89 void tarjans(int n) 90 { 91 int i; 92 bcnt = time = 0; 93 while(!st.empty())st.pop(); 94 memset(dfn,0,sizeof(dfn)); 95 96 memset(inst,0,sizeof(inst)); 97 memset(belong,0,sizeof(belong)); 98 for(i = 1;i <= n;i++) 99 if(!dfn[i])tarjan(i); 100 } 101 struct node 102 { 103 int s,point; 104 }; 105 106 107 108 struct node bfs(int s) 109 { 110 int i; 111 for(i = 1;i <= bcnt;i++) 112 vis[i] = 0; 113 queue <struct node>q; 114 struct node p; 115 p.s = 0;p.point = s; 116 q.push(p); 117 vis[s] = 1; 118 struct node max; 119 max.s = 0; 120 121 while(!q.empty()) 122 { 123 struct node now,temp; 124 now = q.front(); 125 q.pop(); 126 127 for(i = 0;i < ng[now.point].size();i++) 128 { 129 int v = ng[now.point][i]; 130 temp.s = now.s+1; 131 temp.point = v; 132 if(!vis[v]) 133 { 134 vis[v] = 1; 135 // cout<<v<<"***"<<endl; 136 137 if(max.s < temp.s) 138 max = temp; 139 q.push(temp); 140 } 141 } 142 } 143 return max; 144 } 145 int main() 146 { 147 int n,m; 148 //freopen("in.txt","r",stdin); 149 while(scanf("%d %d",&n,&m)&&(n||m)) 150 { 151 int a,b,i; 152 init(n); 153 memset(vis,0,sizeof(vis)); 154 for(i = 0;i < m;i++) 155 { 156 scanf("%d %d",&e[i].u,&e[i].v); 157 addedge(e[i].u,e[i].v,1); 158 addedge(e[i].v,e[i].u,1); 159 } 160 tarjans(n); 161 162 163 for(i = 1;i <= n;i++) 164 { 165 ng[i].clear(); 166 } 167 168 for(i = 0;i < m;i++) 169 { 170 if(belong[e[i].u] == belong[e[i].v]) 171 continue; 172 ng[belong[e[i].u]].push_back(belong[e[i].v]); 173 ng[belong[e[i].v]].push_back(belong[e[i].u]); 174 } 175 struct node max; 176 max = bfs(1); 177 max = bfs(max.point); 178 printf("%d ",bcnt-max.s-1); 179 } 180 return 0; 181 }