首先双连通缩点建立新图（顺带求原图的总的桥数，其实由于原图是一个强连通图，所以桥就等于缩点后的边）
此时得到的图类似树结构，对于新图求一次直径，也就是最长链。
我们新建的边就一定是连接这条最长链的首尾，这样就将原图的桥减少了直径个。
#include #include #include #include #include #include using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define maxn 200005 #define maxm 2000005 struct node { int to,vis,next; }e[maxm],e2[maxm]; int head[maxn],head2[maxn],en,en2; int belong[maxn],vis[maxn],dfn[maxn],low[maxn],cnt,bridge,col,stack[maxn],top; bool use[maxn]; void add(int a,int b) { e[en].to=b; e[en].vis=0; e[en].next=head[a]; head[a]=en++; e[en].to=a; e[en].vis=0; e[en].next=head[b]; head[b]=en++; } void add2(int a,int b) { e2[en2].to=b; e2[en2].next=head2[a]; head2[a]=en2++; e2[en2].to=a; e2[en2].next=head2[b]; head2[b]=en2++; } void init() { top=cnt=col=bridge=en2=en=0; memset(vis,0,sizeof(vis)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(use,0,sizeof(use)); memset(head2,-1,sizeof(head2)); memset(head,-1,sizeof(head)); } void Tarjan (int u) { int v; vis[u] = 1; dfn[u] = low[u] = ++cnt; stack[top++] = u; for (int i = head[u];i != -1;i = e[i].next) { v = e[i].to; if (e[i].vis) continue; e[i].vis = e[i^1].vis = 1; if (vis[v] == 1) low[u] = min(low[u],dfn[v]); if (!vis[v]) { Tarjan (v); low[u] = min(low[u],low[v]); if (low[v] > dfn[u]) bridge ++; } } if (dfn[u] == low[u]) { ++col; do{ v = stack[--top]; vis[v] = 0; belong[v] = col; }while (u != v); } } int len,st; void dfs(int now,int sum,int fa) { use[now]=1; if(sum>len) {st=now;len=sum;} for(int i=head2[now];~i;i=e2[i].next) { if(!use[e2[i].to]) dfs(e2[i].to,sum+1,now); } } inline int ReadInt() { char ch = getchar(); int data = 0; while (ch < '0' || ch > '9') { ch = getchar(); } do { data = data*10 + ch-'0'; ch = getchar(); }while (ch >= '0' && ch <= '9'); return data; } int main() { int n,m,a,b; while(scanf("%d%d",&n,&m)!=EOF) { if(!n&&!m) break; init(); for(int i=1;i<=m;i++) { a=ReadInt(); b=ReadInt(); add(a,b); } Tarjan(1); for(int i=1;i<=n;i++) for(int j=head[i];~j;j=e[j].next) { int to=e[j].to; if(belong[to]!=belong[i]) {add2(belong[to],belong[i]);} } len=0;dfs(1,0,-1); memset(use,0,sizeof(use)); len=0;dfs(st,0,-1); printf("%d\n",bridge-len); } return 0; }