点双连通分量

概念及性质：

在一个连通图中任选两点，如果它们之间至少存在两条“点不重复”的路径，则称为点双连通分量。在这个图上去掉任意一个点，整个图仍然连通。即点双连通分量中不存在割点。

不同的点双连通分量最多只有一个公共点，即某个割点；

任意割点都是至少两个点双连通分量的公共点。

在一个无向图中求点双连通分量数量的方法：

容易发现，在找到一个割点时，已经完成了一次对某个极大点双连通子图的访问。那么我们在DFS的过程中把遍历过的点保存起来，就可以得到这个点双连通分量。用栈来保存DFS访问过程是最合理的，在求解割点的过程中，用一个栈来保存遍历过的边（注意是边，不是点，因为割点是多个点双连通分量的公共点，如果入栈的是点，这个割点弹出来之后，就只能给一个点双连通分量了，它连接的其他点双连通分量就会少了这个点）。

参考代码：

struct Edge{int u,v;Edge(int u=0,int v=0):u(u),v(v){}
}e[maxm];
int n,m,stamp,dfn[maxn],low[maxn],iscut[maxn],bccno[maxn];
int scnt,stack[maxm],bcc_cnt;
vector<int> vec[maxn],bcc[maxn];void tarjan(int index,int fa)
{int child=0,tmp;dfn[index]=low[index]=++stamp;for(int i=0;i<vec[index].size();i++){tmp=e[vec[index][i]].v;if(!dfn[tmp]){stack[++scnt]=vec[index][i],child++;tarjan(tmp,index);low[index]=min(low[index],low[tmp]);if(low[tmp]>=dfn[index]){iscut[index]=1;bcc[++bcc_cnt].clear();while(1){int num=stack[scnt--];if(bccno[e[num].u]!=bcc_cnt){bcc[bcc_cnt].push_back(e[num].u);bccno[e[num].u]=bcc_cnt;}if(bccno[e[num].v]!=bcc_cnt){bcc[bcc_cnt].push_back(e[num].v);bccno[e[num].v]=bcc_cnt;}if(e[num].u==index && e[num].v==tmp)break;}}}else if(dfn[tmp]<dfn[index] && tmp!=fa){stack[++scnt]=vec[index][i];low[index]=min(low[index], dfn[tmp]);}}if(fa<0 && child==1)iscut[index]=0;
}void find_bcc()
{// 割顶的bccno值无意义 memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(iscut,0,sizeof(iscut));memset(bccno,0,sizeof(bccno));memset(bcc,0,sizeof(bcc));stamp=scnt=bcc_cnt=0;for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,-1);
}

例题：poj 1523

题意：求一个图中有多少个割点？每个割点能把图分成几个点双连通分量？

直接上代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e3 + 10;
const int INF = 0x3fffffff;
const int mod = 1000000007;
struct Edge {int v, next;
} edge[maxn * 2];
int head[maxn];
int cnt;
void addedge (int u, int v) {++cnt;edge[cnt].v = v;edge[cnt].next = head[u];head[u] = cnt;
}
int dfn;        // dfs遍历次序
int num[maxn];  // 每个点的dfs次序
int low[maxn];  // low[v]表示v及v的后代能退回的num最小的祖先
int subnets[maxn];  // 每个割点的点双连通分量
bool hasCut;  // 是否发现割点
int V;        // 最大的顶点编号
int root;     // 根节点void dfs(int u, int fa) {int child = 0;      // 不相连的子树数量num[u] = low[u] = ++dfn;  // 记录该点的遍历次序，该点的low值初始等于numfor (int i = head[u]; i != -1; i = edge[i].next) {int v = edge[i].v;if (!num[v]) {child++;dfs(v, u);low[u] = min(low[u], low[v]);   // 用后代的返回值更新low值if ((u == root && child >= 2) || (u != root && low[v] >= num[u])) {  // 判断割点hasCut = true;subnets[u]++;   // 这个割点的点双连通分量加1/*u->v  该边导致u成为割点 当dfn[u]==low[v]时u->v为返祖边,u、v处于同一双连通分量中当dfn[u]<low[v]时u->v为割边删除割点u产生的连通数目为：u所在的连通分量数目 + 与u所连接的割边的数目 + 1（边:fa->u）*/}} else if (v != fa) {   // 处理回退边low[u] = min(low[u], num[v]);}}}void solve() {int u, v, cas = 0;while (true) {cnt = 0;memset(num, 0, sizeof num);memset(low, 0, sizeof low);memset(subnets, 0, sizeof subnets);memset(head, -1, sizeof head);hasCut = false;dfn = 0;V = -1;while (cin >> u, u) {   // 建图cin >> v;addedge(u, v);addedge(v, u);V = max(max(u, v), V);}if (V == -1) {      // 本轮输入没有任何顶点，输入结束return;}root = V;dfs(root, -1);      // dfs tarjancout << "Network #" << ++cas << endl;if (hasCut) {for (int i = 1; i <= V; i++) {if (subnets[i] > 0) {cout << "  SPF node " << i << " leaves " << subnets[i] + 1 << " subnets" << endl;}}} else {cout << "  No SPF nodes\n";}cout << endl;}}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout << fixed;cout.precision(18);solve();return 0;
}

边双连通分量

概念及性质：

在一个连通图中任选两点，如果它们之间至少存在两条“边不重复”的路径，则称为边双连通分量。在这个图上去掉任意一个边，整个图仍然连通。即边双连通分量中不存在割边（桥）。

割顶只能属于一个分量，请与割边区分。

在一个无向图中有多少个边双连通分量？至少应该添加多少条边，才能使任意两个边双连通分量之间都是双连通的，也就是图G变为双连通？ 

边双连通分量的计算使用了“缩点”思想。就是将每个边双连通分量都看作一个“缩点”。具体实现如下：

（1） 首先找出图中所有的边双连通分量。在DFS过程中，计算每个点的low值，low值相同的点必定在同一个边双连通分量中（low值的定义见之前割点割边的文章）。DFS结束后，有多少low值，就有多少个边双连通分量。

（2）把每个边双连通分量都看作一个点，即把那些low值相同的点合并为一个缩点。这些缩点形成了一棵树。

（3）问题被转化为：至少在缩点树上增加多少条边，能使这棵树变为一个边双连通图。因为要成为一个边双连通图，每个点的度数都必须大于1，容易推导出：至少增加的边数=（度数为1的节点数+1）/2。

例题：poj 3352

题意：给定一个无向图G，图中没有重边。问添加几条边才能使无向图变成边双连通图。

代码：

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e3 + 10;
const int INF = 0x3fffffff;
const int mod = 1000000007;
int n, m, low[maxn], num[maxn], dfn;
vector<int> G[maxn];
int degree[maxn];   // 缩点的度数void dfs(int u, int fa) {   // 计算每个点的low值，low值相同的点必定在同一个边双连通分量中low[u] = num[u] = ++dfn;for (int i = 0; i < G[u].size(); i++) {int v = G[u][i];if (!num[v]) {dfs(v, u);low[u] = min(low[u], low[v]);} else if (v != fa) {low[u] = min(low[u], num[v]);}}
}int tarjan() {  // 将每个边双连通分量缩点，并计算每个缩点的度数memset(degree, 0, sizeof degree);for (int i = 1; i <= n; i++) {      // 把有相同low值的点看作一个缩点for (int j = 0; j < G[i].size(); j++) {if (low[i] != low[G[i][j]]) {degree[low[i]]++;}}}int res = 0;for (int i = 1; i <= n; i++) {      // 统计度数为1的缩点个数if (degree[i] == 1) {res++;}}return res;
}void solve() {while (cin >> n >> m) {memset(num, 0, sizeof num);memset(low, 0, sizeof low);for (int i = 1; i <= n; i++) {G[i].clear();}for (int i = 1; i <= m; i++) {int u, v;cin >> u >> v;G[u].push_back(v);G[v].push_back(u);}dfn = 0;dfs(1, -1);int ans = tarjan();cout << (ans + 1) / 2 << endl;  // cout << (ans % 2 == 0 ? ans / 2 : ans / 2 + 1) << endl}
}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout << fixed;cout.precision(18);solve();return 0;
}