【概念】

1.雙連通分量：對于一個無向圖，其邊/點連通度大于1，滿足任意兩點之間，能通過兩條或兩條以上沒有任何重復邊的路到達的圖，即刪掉任意邊/點后，圖仍是連通的

2.分類：

? ? 1）點雙連通圖：點連通度大于 1 的圖

? ? 2）邊雙連通圖：邊連通度大于 1 的圖

【原理】

1.求點雙連通分量

求點雙連通分量可以在求割點的同時用棧維護。

在搜索圖時，每找到一條樹枝邊或后向邊(非橫叉邊)，就把這條邊加入棧中。如果遇到滿足 dfn(u)<=low(v)，說明 u 是一個割點，同時把邊從棧頂一個個取出，直到遇到了邊 (u,v)，取出的這些邊與其關聯(lián)的點，就組成一個點雙連通分支。

割點可以屬于多個點雙連通分支，其余點和每條邊只屬于且屬于一個點雙連通分支。

2.求邊雙連通分量

求邊雙連通分量時，需要先求出橋，然后把橋全部去掉，原圖變成多個連通塊，此時每個連通塊就是一個邊雙連通分量。

橋不屬于任何一個邊雙連通分量，其余的邊和每個頂點都屬于且只屬于一個邊雙連通分量

【過程】

1.求點雙連通分量

1）Tarjan 求割點

2）每找到一個割點，將它上面的所有點彈出棧，所得到的點集就是點雙連通分量

2.求邊雙連通分量

1）Tarjan 找橋

2）刪除橋

3）剩余各部分即為邊雙連通分量

【實現(xiàn)】

1.求點雙連通分量

int n,m; vector<int> G[N]; vector<int> bcc[N];//包含i號點雙連通分量的所有結(jié)點 int dfn[N]; bool iscut[N];//記錄i結(jié)點是否是割點 int bccno[N];//記錄第i個點屬于第幾號點雙連通分量 int block_cnt;//時間戳 int bcc_cnt;//記錄點雙連通分量個數(shù) struct Edge {int x;int y; }; stack<Edge> S; int Tarjan(int x,int father) {int lowx=dfn[x]=++block_cnt;int child=0;//子節(jié)點數(shù)目for(int i=0; i<G[x].size(); i++) {int y=G[x][i];//當前結(jié)點的下一結(jié)點Edge e;e.x=x;e.y=y;if(dfn[y]==0) { //若未被訪問過S.push(e);child++;//未訪問過的節(jié)點才能算是x的孩子int lowy=Tarjan(y,x);lowx=min(lowx,lowy);if(lowy>=dfn[x]) {iscut[x]=true;//x點是割點bcc_cnt++;bcc[bcc_cnt].clear();while(true) {Edge temp=S.top();S.pop();if(bccno[temp.x]!=bcc_cnt) {bcc[bcc_cnt].push_back(temp.x);bccno[temp.x]=bcc_cnt;}if(bccno[temp.y]!=bcc_cnt) {bcc[bcc_cnt].push_back(temp.y);bccno[temp.y]=bcc_cnt;}if(temp.x==x && temp.y==y)break;}}} else if(dfn[y]<dfn[x] && y!=father) { //y!=father確保了(x,y)是從x到y(tǒng)的反向邊S.push(e);lowx=min(lowx,dfn[y]);}}if(father<0 && child==1 )//x若是根且孩子數(shù)<=1,那x就不是割點iscut[x]=false;return lowx; } int main() {scanf("%d%d",&n,&m);for(int i=0; i<n; i++)G[i].clear();while(m--) {int x,y;scanf("%d%d",&x,&y);G[x].push_back(y);G[y].push_back(x);}bcc_cnt=0;block_cnt=0;memset(dfn,0,sizeof(dfn));memset(iscut,0,sizeof(iscut));memset(bccno,0,sizeof(bccno));for(int i=0; i<n; i++)if(!dfn[i])Tarjan(i,-1);printf("點-雙連通分量一共%d個\n",bcc_cnt);for(int i=1; i<=bcc_cnt; i++){printf("第%d個點-雙連通分量包含以下點:\n",i);sort(&bcc[i][0],&bcc[i][0]+bcc[i].size()); //對vector排序,使輸出的點從小到大for(int j=0; j<bcc[i].size(); j++)printf("%d ",bcc[i][j]);printf("\n");}return 0; }

2.求邊雙連通分量

struct Edge {int x;int yl } edge[N]; int n,m; int dfn[N],low[N]; int bccno[N]; vector<int> G[N],bcc[N]; int sig,block_cnt; bool g[N][N],isbridge[N]; void tarjan(int x,int father) {dfn[x]=low[x]=++block_cnt;for(int i=0; i<G[x].size(); i++) {int y=edge[G[x][i]].y;if(!dfn[y]) {tarjan(y,x);low[x]=min(low[x],low[y]);if(low[y]>dfn[x]) {isbridge[G[x][i]]=1;isbridge[G[x][i]^1]=1;}} else if(dfn[y]<dfn[x] && y!=father)low[x]=min(low[x], dfn[y]);} } void dfs(int x) {dfn[x]=1;bccno[x]=sig;for(int i=0; i<G[x].size(); i++) {int y=G[x][i];if(isbridge[y])continue;if(!dfn[edge[y].y])dfs(edge[y].y);} } int main() {scanf("%d%d",&n,&m);for(int i=0; i<n; i++)G[i].clear();while(m--) {int x,y;scanf("%d%d",&x,&y);G[x].push_back(y);}sig=0;block_cnt=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(isbridge,0,sizeof(isbridge));memset(bccno,0,sizeof(bccno));memset(bcc,0,sizeof(bcc));for(int i=1; i<=n; i++) //先DFS找橋if(!dfn[i])tarjan(i, -1);memset(dfn,0,sizeof(dfn));for(int i=1; i<=n; i++){ //再DFS找邊雙連通分量if(!dfn[i]) {sig++;dfs(i);}}printf("%d\n",sig);//邊雙連通分量個數(shù)return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的图论 —— 图的连通性 —— Tarjan 求双连通分量的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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