雙連通分量
點(diǎn)_雙連通分量 BCC
對(duì)于一個(gè)連通圖,如果任意兩點(diǎn)至少存在兩條“點(diǎn)不重復(fù)”的路徑,則說(shuō)圖是點(diǎn)雙連通的（即任意兩條邊都在一個(gè)簡(jiǎn)單環(huán)中）,點(diǎn)雙連通的極大子圖稱為點(diǎn)_雙連通分量分预。 通常來(lái)說(shuō),如果要求任意兩條邊在同一個(gè)簡(jiǎn)單環(huán)中,那么就是求點(diǎn)-雙連通
易知每條邊屬于一個(gè)連通分量，且連通分量之間最多有一個(gè)公共點(diǎn)秕重，且一定是割頂叉袍。
#include <cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int MAXN=10010;
vector<int> graph[MAXN];
int dfn[MAXN];//第一次訪問(wèn)的時(shí)間戳
int clocks;//時(shí)間戳
int isCut[MAXN];//標(biāo)記節(jié)點(diǎn)是否為割頂
struct Edge
{
int u,v;
Edge(){}
Edge(int u,int v):u(u),v(v){}
};
vector<Edge> edge;//DFS訪問(wèn)過(guò)的邊
vector<int> bcc[MAXN];//點(diǎn)_雙連通分量
int bccno[MAXN];//節(jié)點(diǎn)屬于的點(diǎn)_雙連通分量的編號(hào)
int bcc_cnt;//點(diǎn)_雙連通分量的數(shù)目
int DFS(int u,int fa)
{
int lowu=dfn[u]=++clocks;
int child=0;
for(int i=0;i<graph[u].size();i++)
{
int v=graph[u][i];
Edge e(u,v);
if(dfn[v]==0)
{
edge.push_back(e);
child++;
int lowv=DFS(v,u);
lowu=min(lowv,lowu);//用后代更新lowu
if(lowv>=dfn[u])//找到了一個(gè)子樹滿足割頂?shù)臈l件
{
isCut[u]=1;
bcc_cnt++;
bcc[bcc_cnt].clear();
while(true)//保存bcc信息
{
Edge ee=edge.back();
edge.pop_back();
//bccno[ee.u]!=bcc_cnt是為了防止重復(fù)加點(diǎn)
if(bccno[ee.u]!=bcc_cnt) { bcc[bcc_cnt].push_back(ee.u); bccno[ee.u]=bcc_cnt;}
if(bccno[ee.v]!=bcc_cnt) {bcc[bcc_cnt].push_back(ee.v);bccno[ee.v]=bcc_cnt;}
if(ee.u==u&&ee.v==v) break;
}
}
}
else if(dfn[v]<dfn[u]&&v!=fa) //用反向邊更新lowu
{
edge.push_back(e);
lowu=min(lowu,dfn[v]);
}
}
if(fa<0&&child==1) isCut[u]=0;
return lowu;
}
void tarjan(int n)
{
bcc_cnt=clocks=0;
memset(dfn,0,sizeof(dfn));
memset(isCut,0,sizeof(isCut));
memset(bccno,0,sizeof(bccno));
memset(bcc,0,sizeof(bcc));
for(int i=1;i<=n;i++)
{
if(dfn[i]==0)
{
DFS(i,-1);
}
}
for(int i=1;i<=bcc_cnt;i++)
{
for(int j=0;j<bcc[i].size();j++)
{
printf("%d ",bcc[i][j]);
}
printf("\n");
}
}
int main()
{
int n,m,a,b;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(graph,0,sizeof(graph));
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
graph[a].push_back(b);
graph[b].push_back(a);
}
tarjan(n);
}
}
邊_雙連通分量 EBC
邊雙連通分量是指任意兩點(diǎn)存在至少兩條"邊不重復(fù)"的路徑的圖,還可以理解為每條邊都至少在一個(gè)簡(jiǎn)單環(huán),即每條邊都不是橋色徘。如果要求某條邊被刪除了,但是圖G能夠在刪除任意一條邊后很洋，仍然是連通的失乾，當(dāng)且僅當(dāng)圖G至少為雙連通的。
對(duì)于邊雙連通分量的求解簡(jiǎn)單多了娩贷，我們先找出所有的橋第晰，并將其做上標(biāo)記。然后在利用dfs遍歷連通分量育勺，只需在遍歷時(shí)不訪問(wèn)橋即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1010;
const int MAXE=2010;
struct Node
{
int to,next;
bool cut;//邊是否為橋
};
Node edge[MAXE];
int head[MAXN];
int cnt;
int dfn[MAXN];
int low[MAXN];
int clocks;
int belong[MAXN];//點(diǎn)屬于哪個(gè)邊連通分量
int blocks;//連通分量數(shù)
void addEdge(int u,int v)
{
edge[cnt].to=v;
edge[cnt].next=head[u];
edge[cnt].cut=false;
head[u]=cnt++;
}
//e是為了去重,e是邊在數(shù)組的位置
//另一種去重為DFS(u,fa),v!=fa,但是有重邊時(shí)可能會(huì)判斷錯(cuò)誤
//比如沒(méi)重邊時(shí),假設(shè)(a,b)是橋,但是如果(a,b)有重邊,那么(a,b)就不是橋了
void DFS(int u,int e)//求出所有的橋
{
low[u]=dfn[u]=++clocks;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(i==(e^1)) continue;//這里只會(huì)去重該邊的反邊,不會(huì)去它的重邊
if(dfn[v]==0)
{
DFS(v,i);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u])
{
edge[i].cut=1;
edge[i^1].cut=1;
}
}
else if(dfn[v]<dfn[u])
{
low[u]=min(low[u],dfn[v]);
}
}
}
void DFS2(int u)//求出每個(gè)點(diǎn)所在的邊連通分量
{
dfn[u]=1;
belong[u]=blocks;
for(int i=head[u];i!=-1;i=edge[i].next)
{
if(edge[i].cut) continue;
if(dfn[edge[i].to]==0) DFS2(edge[i].to);
}
}
void work(int n)
{
memset(dfn,0,sizeof(dfn));
memset(belong,0,sizeof(belong));
clocks=blocks=0;
for(int i=1;i<=n;i++)
{
if(dfn[i]==0)
{
DFS(i,-1);
}
}
memset(dfn,0,sizeof(dfn));
for(int i=1;i<=n;i++)
{
if(dfn[i]==0)
{
blocks++;
DFS2(i);
}
}
}
int main()
{
int n,m,a,b;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(head,-1,sizeof(head));
cnt=0;
for(int i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
addEdge(a,b);
addEdge(b,a);
}
work(n);
}
}
還有一種辦法是棧模擬,直接在DFS里面求出邊連通分量,基于一個(gè)這樣的事實(shí),橋的端點(diǎn)的dfn[u]=low[u]
簡(jiǎn)要證明以下:
low[u]表示u及其后代能連回的最早的祖先的dfn值,所以low[u]<=dfn[u]總是成立罗岖。假設(shè)對(duì)于橋的一個(gè)端點(diǎn)u,low[u]!=dfn[u],即low[u]<dfn[u],說(shuō)明u可以連到u的父節(jié)點(diǎn)或者u通過(guò)u的某個(gè)子節(jié)點(diǎn)通過(guò)返祖邊連到u的父節(jié)點(diǎn),現(xiàn)在刪除這個(gè)橋,但是u還可以連接到u的父節(jié)點(diǎn)或者u通過(guò)u的子代通過(guò)返祖邊連回到u的父節(jié)點(diǎn),根據(jù)橋的性質(zhì),刪除了橋后u與u的父節(jié)點(diǎn)不能連通,這與橋的性質(zhì)有矛盾,所以假設(shè)不成立,即low[u]==dfn[u]
#include<cstdio>
#include<stack>
#include<cstring>
using namespace std;
const int MAXN=1010;
const int MAXE=2010;
struct Node
{
int to,next;
bool cut;
};
Node edge[MAXE];
int head[MAXN];
int low[MAXN],dfn[MAXN],onStack[MAXN];
int cnt,clocks;
stack<int> sta;
int belong[MAXN];
int blocks;
void addEdge(int u,int v)
{
edge[cnt].to=v;
edge[cnt].next=head[u];
edge[cnt].cut=false;
head[u]=cnt++;
}
void DFS(int u,int e)
{
low[u]=dfn[u]=++clocks;
onStack[u]=1;
sta.push(u);
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(e==(i^1)) continue;
if(dfn[v]==0)
{
DFS(v,i);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u])
{
edge[i].cut=true;
edge[i^1].cut=true;
}
}
else if(onStack[v]&&dfn[v]<dfn[u])//v在棧中涧至，說(shuō)明(u,v)是返祖邊
{
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u])//說(shuō)明u是橋的端點(diǎn),所以將u所在的邊連通分量出棧
{
blocks++;
while(true)
{
int curr=sta.top();
sta.pop();
onStack[curr]=0;//出棧
belong[curr]=blocks;
if(curr==u) break;
}
}
}
void work(int n)
{
memset(dfn,0,sizeof(dfn));
memset(onStack,0,sizeof(onStack));
clocks=0;
while(!sta.empty()) sta.pop();
memset(belong,0,sizeof(belong));
blocks=0;
for(int i=1;i<=n;i++)
{
if(dfn[i]==0)
{
DFS(i,-1);
}
}
}
int main()
{
int n,m,a,b;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(head,-1,sizeof(head));
cnt=0;
for(int i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
addEdge(a,b);
addEdge(b,a);
}
work(n);
}
}
