思路：將以橋為分界的所有連通分支進行縮點，得到一顆樹，求出樹的直徑。再用樹上的點減去直徑，再減一

#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;//一開始沒加這個判斷,一直WAedge[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\n",solve());}return 0; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/wangfang20/p/3215313.html

總結(jié)

以上是生活随笔為你收集整理的hdu 4612 边连通度缩点+树的最长路径的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。