題目鏈接：點擊查看

題目大意：給出一個由n個點組成的無向圖，現在有m次操作，每次操作都會向圖中增加一條無向邊，每次操作后詢問當前圖中有多少個橋

題目分析：題意很好理解，思路也很好想，就是代碼量有點小多（好幾個模板拼拼湊湊出來的）

既然提到橋了，那么肯定先強連通縮一波點，將圖重構成一棵樹，求出原圖中有多少個橋，隨后每次操作都會加邊，如果新邊的兩個端點屬于同一個強連通塊中，那么不會對答案做出貢獻，直接輸出答案就行了，如果不在同一個連通塊中，假設兩個點為x和y，那么加上這條邊后，會對x->lca(x,y)->y這條邊造成影響，具體影響就是這條邊上的所有橋都成為一個連通分量了，故最后答案需要減去這條路徑上的所有橋，并且將其標記一下，防止后續操作重復貢獻

現在我們就是需要利用算法與數據結構實現上述操作了，很顯然強連通縮點用tarjan，求lca用樹上倍增就行，單純因為好寫。。最后在路徑上更新答案可以暴力，因為這個題目的數據比較水，就是直接一個點一個點的走，時間復雜度為O(m+q*n)，不過完全可以用并查集優化一下，其實用到并不是真的并查集，而是使用并查集路徑壓縮的思路，這樣就能避免重復經過已經做出過貢獻的橋了，時間復雜度優化為了O(m+q*logn)了，最后就是如何標記路徑，這里我選擇將邊權映射給節點，因為我們在樹上往上走的時候都是沿著父節點向上走，每個點的父節點都是唯一的，所以我們不妨將(父節點-當前節點)的這條路徑映射到當前節點上來，具體實現看代碼吧，就是多個模板拼湊起來的，代碼量就比較多了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;const int M=4e5+100;struct Egde {int to,next; }edge[M],edge2[M];int head[N],head2[N],low[N],dfn[N],c[N],f[N],num,cnt,cnt2,dcc,n,m,limit;bool bridge[M],vis[N];void addedge(int u,int v) {edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++; }void addedge2(int u,int v) {edge2[cnt2].to=v;edge2[cnt2].next=head2[u];head2[u]=cnt2++; }void tarjan(int u,int in_edge) {dfn[u]=low[u]=++num;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if(!dfn[v]){tarjan(v,i);low[u]=min(low[u],low[v]);if(low[v]>dfn[u])bridge[i]=bridge[i^1]=true;}else if(i!=(in_edge^1))low[u]=min(low[u],dfn[v]);} }void dfs(int u) {c[u]=dcc;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if(c[v]||bridge[i])continue;dfs(v);} }void init() {limit=log2(n)+1;cnt2=cnt=num=dcc=0;memset(head2,-1,sizeof(head2));memset(head,-1,sizeof(head));memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));memset(bridge,false,sizeof(bridge));memset(c,0,sizeof(c));memset(vis,false,sizeof(vis)); }void solve() {for(int i=1;i<=n;i++)//找橋 if(!dfn[i])tarjan(i,0);for(int i=1;i<=n;i++)//縮點 if(!c[i]){dcc++;dfs(i);} }void build()//縮點+連邊 {solve();memset(f,-1,sizeof(f));for(int i=0;i<cnt;i+=2){int u=edge[i^1].to;int v=edge[i].to;if(c[u]==c[v])continue;addedge2(c[u],c[v]);addedge2(c[v],c[u]);} }int deep[N],dp[N][20];void dfs2(int u,int fa,int dep) {deep[u]=dep;dp[u][0]=fa;f[u]=fa;for(int i=1;i<=limit;i++)dp[u][i]=dp[dp[u][i-1]][i-1];for(int i=head2[u];i!=-1;i=edge2[i].next){int v=edge2[i].to;if(v==fa)continue;dfs2(v,u,dep+1);} }int LCA(int x,int y) {if(deep[x]<deep[y])swap(x,y);for(int i=limit;i>=0;i--)if(deep[x]-deep[y]>=(1<<i))x=dp[x][i];if(x==y)return x;for(int i=limit;i>=0;i--)if(dp[x][i]!=dp[y][i]){x=dp[x][i];y=dp[y][i];}return dp[x][0]; }int cal(int x,int y) {int lca=LCA(x,y);int ans=0;while(deep[x]>deep[lca]){if(!vis[x]){ans++;vis[x]=true;}int xx=f[x];f[x]=lca;x=xx;}while(deep[y]>deep[lca]){if(!vis[y]){ans++;vis[y]=true;}int yy=f[y];f[y]=lca;y=yy;}return ans; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int kase=0;while(scanf("%d%d",&n,&m)!=EOF&&n+m){init();while(m--){int u,v;scanf("%d%d",&u,&v);addedge(u,v);addedge(v,u);}build();dfs2(1,0,0);int ans=dcc-1;scanf("%d",&m);printf("Case %d:\n",++kase);while(m--){int u,v;scanf("%d%d",&u,&v);if(c[u]!=c[v])//不一個連通塊內ans-=cal(c[u],c[v]);printf("%d\n",ans);}}return 0; }

?

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的POJ - 3694 Network(边双缩点+LCA+并查集优化)的全部內容，希望文章能夠幫你解決所遇到的問題。

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