<題目鏈接>

<轉載于 >>>? >

題目大意：

有n個牧場，Bessie 要從一個牧場到另一個牧場，要求至少要有2條獨立的路可以走。現已有m條路，求至少要新建多少條路，使得任何兩個牧場之間至少有兩條獨立的路。兩條獨立的路是指：沒有公共邊的路，但可以經過同一個中間頂點。

解題分析：

在同一個邊雙連通分量中，任意兩點都有至少兩條獨立路可達，所以同一個邊雙連通分量里的所有點可以看做同一個點。

縮點后，新圖是一棵樹，樹的邊就是原無向圖的橋。

現在問題轉化為：在樹中至少添加多少條邊能使圖變為雙連通圖。

結論：添加邊數=（樹中度為1的節點數+1）/2

具體方法為，首先把兩個最近公共祖先最遠的兩個葉節點之間連接一條邊，這樣可以把這兩個點到祖先的路徑上所有點收縮到一起，因為一個形成的環一定是雙連通的。然后再找兩個最近公共祖先最遠的兩個葉節點，這樣一對一對找完，恰好是(leaf+1)/2次，把所有點收縮到了一起。

#include <cstdio> #include <cstring> #include <algorithm> using namespace std;const int N = 5e3+5 , M = 1e4+5; #define clr(a,b) memset(a,b,sizeof(a)) struct Edge{int to,next; }edge[M<<1];int head[N],low[N],dfn[N],belong[N],deg[N],stk[N],instk[N]; int n,m,tot,cnt,top,scc; void addEdge(int u,int v){edge[tot].to=v,edge[tot].next=head[u];head[u]=tot++; } void init(){tot=cnt=top=scc=0;clr(head,-1);clr(low,0);clr(dfn,0);clr(instk,0);clr(deg,0); } void Tarjan(int u,int fa){low[u]=dfn[u]=++cnt;stk[++top]=u;instk[u]=1;for(int i=head[u];~i;i=edge[i].next){int v=edge[i].to;if(i==(fa^1))continue; //不能用搜索樹上的邊來更新low值，這種寫法能夠用來處理重邊的情況if(!dfn[v]){Tarjan(v,i);low[u]=min(low[u],low[v]);}else if(instk[v]) //此時棧里的所有元素均屬于同一邊雙連通分量,找連通分量的根的時候一定要規定這點，否則可能會與其他連通分量的dfn比較low[u]=min(low[u],dfn[v]); //low值全部等于該雙連通分量中最先遍歷的點dfn值 }if(dfn[u]==low[u]){++scc; while(true){int v=stk[top--];instk[v]=0;belong[v]=scc; //將該聯通塊中的所有點全部縮點染色if(v==u)break;} } } int main(){while(scanf("%d%d",&n,&m)!=EOF){init();for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);addEdge(u,v),addEdge(v,u);}Tarjan(1,-1);for(int i=1;i<=n;i++){for(int j=head[i];j!=-1;j=edge[j].next){int v=edge[j].to;if(belong[i]!=belong[v])deg[belong[i]]++; //求出縮點后每個點的度 }}int sum=0;for(int i=1;i<=scc;i++)if(deg[i]==1)sum++; //尋找度為1的葉子節點 int ans=(sum+1)/2; printf("%d\n",ans);} }

?

?

?

2018-11-07

轉載于:https://www.cnblogs.com/00isok/p/9919653.html

總結

以上是生活随笔為你收集整理的POJ 3177 Redundant Paths (边双连通+缩点)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。