思路:将以桥为分界的所有连通分支进行缩点,得到一颗树,求出树的直径。再用树上的点减去直径,再减一
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<queue> #define Maxn 210110 #define Maxm 2501000 using namespace std; int index[Maxn],vi[Maxn],dfn[Maxn],low[Maxn],e,n,lab=0,Stack[Maxn],top,num,head[Maxn],ans,id[Maxn]; void init() { memset(index,-1,sizeof(index)); memset(head,-1,sizeof(head)); memset(vi,0,sizeof(vi)); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); e=lab=top=num=ans=0; } struct Edge{ int from,to,next,v; }edge[Maxm]; void addedge(int from, int to) { edge[e].v=0; edge[e].from=from; edge[e].to=to; edge[e].next=index[from]; index[from]=e++; edge[e].v=0; edge[e].to=from; edge[e].from=to; edge[e].next=index[to]; index[to]=e++; } void add(int from,int to) { edge[e].v=0; edge[e].from=from; edge[e].to=to; edge[e].next=head[from]; head[from]=e++; edge[e].v=0; edge[e].to=from; edge[e].from=to; edge[e].next=head[to]; head[to]=e++; } int Count(int u) { ++num; int i; do {//将该连通分量进行标记 i=Stack[--top]; id[i]=num; }while(i!=u); return 0; } int dfs(int u) { dfn[u]=low[u]=++lab; Stack[top++]=u; int i,j,temp; for(i=index[u];i!=-1;i=edge[i].next) { temp=edge[i].to; if(edge[i].v) continue;//一开始没加这个判断,一直WA edge[i].v=edge[i^1].v=1; if(!dfn[temp]) { dfs(temp); low[u]=min(low[u],low[temp]); } low[u]=min(low[u],dfn[temp]); } if(dfn[u]==low[u]) Count(u); return 0; } int maxLen(int u) { vi[u]=1; int i,j,temp=0,Max=0,lMax=0; for(i=head[u];i!=-1;i=edge[i].next) { if(!vi[edge[i].to]) { temp=maxLen(edge[i].to); if(temp+1>=Max) { lMax=Max; Max=temp+1; } else { if(temp+1>lMax) lMax=temp+1; } if(Max+lMax>ans) ans=Max+lMax; } } return Max; } int solve() { int i,j,u,v,ed; dfs(1); ed=e; e=0; for(i=0;i<ed;i+=2) { u=id[edge[i].from]; v=id[edge[i].to]; add(u,v); } memset(vi,0,sizeof(vi)); ans=0; maxLen(1); return num-1-ans; } int main() { int m,i,j,a,b; while(scanf("%d%d",&n,&m),n||m) { init(); for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); addedge(a,b); } printf("%d ",solve()); } return 0; }