无向图割点/桥&双连通分量
无向图图中所有边要么是树边，要么是反向边。
割点的条件
- 当树根有两个及以上子节点时，树根是割点。
- 非根节点u为割点，当且仅当该点存在一个子节点v，且v及其所有后代都没有反向边连回u的祖先。（连回u不算，此时u是割点）
用LOW[x]代表x及其后代能连回祖先最小的DFN值，那么上述条件即为u存在一个子节点v，使得LOW[v] DFN[u].
另外，若v的后代最早只能连到v自己，那么边(u,v)是桥。
void tarjan(int x,int fa)
{
DFN[x] = LOW[x] = ++xu;
int cntz = 0;
for(int i = 0;i < G[x].size();i++)
{
int to = G[x][i];
if(!DFN[to])
{
tarjan(to,fa);
LOW[x] = homin(LOW[x],LOW[to]);
if(LOW[to] >= DFN[x] && x != fa) iscut[x] = 1;//此时G[x]为桥
if(x == fa) cntz++;//如果是根节点，计算子节点个数
}
LOW[x] = homin(LOW[x],DFN[to]);
}
if(cntz >= 2) iscut[x] = 1;//根节点并且有两个及以上子节点
return ;
}例题 POJ1523
给你一个联通网路，求出这个网络所有割点的编号，以及如果删除这个割点之后所对应的联通分量数.求出所有割点后枚举要删除的割点然后dfs就行了.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <algorithm>
#define MAXN 1050
#define INF 0x3f3f3f3f
#define lovelive long long int
inline int homax(int a,int b)
{
if(a > b) return a;
return b;
}
inline int homin(int a,int b)
{
if(a > b) return b;
return a;
}
using namespace std;
vector<int> G[MAXN];
int DFN[MAXN],LOW[MAXN],iscut[MAXN];
bool vis[MAXN];
int xu = 0;
const int N = 1000;
bool inp[MAXN];
void tarjan(int x,int fa)
{
DFN[x] = LOW[x] = ++xu;
int cntz = 0;
for(int i = 0;i < G[x].size();i++)
{
int to = G[x][i];
if(!DFN[to])
{
tarjan(to,fa);
LOW[x] = homin(LOW[x],LOW[to]);
if(LOW[to] >= DFN[x] && x != fa) iscut[x] = 1;
if(x == fa) cntz++;
}
LOW[x] = homin(LOW[x],DFN[to]);
}
if(cntz >= 2) iscut[x] = 1;
return ;
}
void dfs(int x,int c)
{
vis[x] = true;
for(int i = 0;i < G[x].size();i++)
{
int to = G[x][i];
if(to == c || vis[to]) continue;
dfs(to,c);
}
return ;
}
int main()
{
int tt = 0;
while(true)
{
memset(inp,false,sizeof inp);
for(int i = 0;i < MAXN;i++) G[i].clear();
xu = 0;
tt++;
int a;
scanf("%d",&a);
if(a == 0) break;
int b;
scanf("%d",&b);
G[a].push_back(b);
G[b].push_back(a);
inp[a] = inp[b] = true;
while(true)
{
int a;
scanf("%d",&a);
if(a == 0) break;
int b;
scanf("%d",&b);
G[a].push_back(b);
G[b].push_back(a);
inp[a] = inp[b] = true;
}
memset(DFN,0,sizeof DFN);
memset(LOW,0,sizeof LOW);
memset(iscut,0,sizeof iscut);
for(int i = 1;i <= N;i++)
{
if(!inp[i]) continue;
if(DFN[i] == 0) tarjan(i,i);
}
printf("Network #%d\n",tt);
bool tb = false;
for(int i = 1;i <= N;i++)
{
if(!inp[i]) continue;
if(iscut[i])
{
tb = true;
memset(vis,false,sizeof vis);
int cnt = 0;
for(int j = 1;j <= N;j++)
{
if(!inp[j]) continue;
if(vis[j] == false && j != i)
{
cnt ++;
dfs(j,i);
}
}
printf(" SPF node %d leaves %d subnets\n",i,cnt);
}
}
if(!tb)
{
printf(" No SPF nodes\n");
}
printf("\n");
}
}双连通分量
点双连通
点双连通(以下三条等价):
- 该连通图的任意两条边存在一个包含这两条边的简单环；
- 该连通图没有割点；
- 对于至少3个点的图，若任意两点有至少两条点不重复路径。
点双连通分量(BCC)
点双连通分量构成对所有边集的一个划分。(一个点可能属于多个点双连通分量,而一个边恰好属于一个)
两个点双连通分量最多只有一个公共点，且必为割点。进一步地，所有点双与割点可抽象为一棵树结构。
不同BCC可能会有公共点,最多只有一个,即割点.任意割点都至少属于两个BCC.
去掉BCC中任意一个点,BCC仍联通.
求每个点双分量的方法类似tarjan,栈存的不是点而是边,因为一个点可能属于多个点双,出栈之后无法将这个点统计到其他点双中,而每个边一定都只属于一个点双.不过这样的点一定是割点,可以用栈存点+对割点特判,
例题 HDU3884
无向图,在最少的点上安装太平井,使删除任意一个点后其他所有点都能到达太平井,并求出最少太平井的安装方案数.点双缩点之后,整个图变成一个无根树.
考虑每个叶节点,在叶节点对应的点双中一定要有一个太平井,否则当删除对应的割点后,这个点双将无法到达任何太平井.并且,这个太平井不能安装在割点,如果安装在割点,删除割点后,这个点双的其他结点不仅无法到达其他叶节点的太平井,自己的太平井也被删了.
同时,对于每个非叶节点,是不需要太平井的.因为非叶节点度数大于1,只删除一个节点是无法让这个节点对应的点双的其他节点到达不了任意一个叶点双的.
缩点后每个节点的度数等于该点双中割点的个数,因为一个割点代表这个点双连接了另一个点双.
最终太平井的个数就是叶节点的个数,方案数就是每个叶节点对应的点双中非割节点的个数的乘积.
特别地,如果整个图只有一个点双,那么应该要修建两个太平井,防止删去唯一的太平井.此时方案数为N*(N-1)/2,其中N为节点个数.
代码:(https://vjudge.net/solution/24521411)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <algorithm>
#include <stack>
#define MAXN 50005
#define INF 0x3f3f3f3f
#define lovelive long long int
#define osu(a,b,i) for(int i = (a);i <= (b);i++)
#define nso(a,b,i) for(int i = (a);i >= (b);i--)
inline int homax(int a,int b)
{
if(a > b) return a;
return b;
}
inline int homin(int a,int b)
{
if(a > b) return b;
return a;
}
using namespace std;
vector<int> G[MAXN];
int DFN[MAXN],LOW[MAXN],iscut[MAXN];
int xu = 0;
vector<int> bcc[MAXN];
int bccno[MAXN];
int bcccnt = 0;
stack<pair<int,int> > S;
void tarjan(int x,int fa)
{
DFN[x] = LOW[x] = ++xu;
int cntz = 0;
for(int i = 0;i < G[x].size();i++)
{
auto p = make_pair(x,G[x][i]);
int to = G[x][i];
if(!DFN[to])
{
S.push(p);
cntz++;
tarjan(to,x);
LOW[x] = homin(LOW[x],LOW[to]);
if(LOW[to] >= DFN[x])
{
iscut[x] = 1;
bcc[++bcccnt].clear();
while(true)
{
auto e = S.top();
S.pop();
if(bccno[e.first] != bcccnt) bcc[bccno[e.first] = bcccnt].push_back(e.first);
if(bccno[e.second] != bcccnt) bcc[bccno[e.second] = bcccnt].push_back(e.second);
if(e.first == x && e.second == G[x][i]) break;
}
}
}else if(DFN[to] < DFN[x] && to != fa)
{
S.push(p);
LOW[x] = homin(LOW[x],DFN[to]);
}
}
if(fa < 0 && cntz < 2) iscut[x] = 0;
return ;
}
int N,M;
int main()
{
scanf("%d",&M);
int ttt = 0;
while(M != 0)
{
ttt++;
N = 0;
osu(0,MAXN-1,i) G[i].clear(),bcc[i].clear();
memset(DFN,0,sizeof DFN);
memset(LOW,0,sizeof LOW);
memset(iscut,0,sizeof iscut);
xu = 0,bcccnt = 0;
memset(bccno,0,sizeof bccno);
osu(1,M,i)
{
int a,b;
scanf("%d%d",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
N = homax(N,homax(a,b));
}
osu(1,N,i)
{
if(!DFN[i]) tarjan(i,-1);
}
lovelive ans1 = 0,ans2 = 1;
osu(1,bcccnt,i)
{
lovelive cnt = 0;
osu(0,bcc[i].size()-1,j)
{
if(iscut[bcc[i][j]]) cnt++;
}
if(cnt == 1)
{
ans1++;
ans2 *= ((lovelive)bcc[i].size()-cnt);
}
}
if(bcccnt == 1)
{
ans1 = 2;
ans2 = ((lovelive)bcc[1].size() * ((lovelive)bcc[1].size()-1))/2;
}
printf("Case %d: %I64d %I64d\n",ttt,ans1,ans2);
scanf("%d",&M);
}
}边双连通
边双连通(以下三条等价):
-
该连通图的任意一条边存在一个包含这条边的简单环；
-
该连通图没有桥；
-
该连通图任意两点有至少两条(边不重复)路径。
边双连通分量(eBCC)
边双连通分量构成对所有点集的一个划分。 两个边双连通分量最多只有一条边，且必为桥。进一步地，所有边双与桥可抽象为一棵树结构。