割点以及割边（桥）
前提：在一张无向连通图中。
割点：删除这一个点以及与这一个点所相连的边，图中的连通分支数增加。
割边（桥）：删除这一个边之后，图中的连通分支树增加。
如果是一般的连通图，那么割点以及桥就是在各个连通块中而言的。
时间戳：在DFS的时候，进行标记。
搜索树：深度优先遍历生成树。（如果不连通，会有搜索森林）
追溯值：对于每一个点，在不走父亲到他的这一条边的情况之下，通过其他的边，所能走到的时间戳最小的点的时间戳。
桥的判定
若无向边 (x, y)是桥，
存在 dfn[x] < low[y]，这说明如果不走这一条边，那么就回不来。
割点的判断
注意有三个条件：（对于非子节点）
- 上面有点；
- 下面有点；
- 存在一个子节点的
low[y] >= dfn[x]
程序实现
#include
using namespace std;
#define N 305
#define M 305
int n, m;
int head[N], tot, ver[M*2], nxt[M*2];
int low[N], dfn[N], num;
bool cut[N];//割点
bool bridge[M*2];//桥
inline void add(int x, int y)
{
ver[++tot] = y;
nxt[tot] = head[x];
head[x] = tot;
}
void tarjan(int x, int in_edge)
{
dfn[x] = ++num;
low[x] = dfn[x];
int flag = 0;
//这个作用在于判断头结点头结点必须要有两颗子树满足low[y] >= dfn[x]才行。
for(int i = head[x]; i; i = nxt[i])
{
int y = ver[i];
if(!dfn[y])
{
tarjan(y, i);
low[x] = min(low[x], low[y]);
if(low[y] > dfn[x]) bridge[i] = bridge[i^1] = true;
if(low[y] >= dfn[x])
{
flag ++;
if(dfn[x] > 1 || flag > 1)
{
cut[x] = true;
}
}
}
else if((in_edge^1) != i)
{
low[x] = min(low[x], dfn[y]);
}
}
}
int main()
{
tot = 1;
scanf("%d%d", &n, &m);
for(int i = 1; i
B 城有 n 个城镇， m 条双向道路。
每条道路连结两个不同的城镇，没有重复的道路，所有城镇连通。
把城镇看作节点，把道路看作边，容易发现，整个城市构成了一个无向图。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 a 和 b，表示城镇 a 和 b 之间存在一条道路。
输出格式
输出共 n 行，每行输出一个整数。
第 i 行输出的整数表示把与节点 i 关联的所有边去掉以后（不去掉节点 i 本身），无向图有多少个有序点 (x ,y )，满足 x 和 y 不连通。
数据范围
n≤ 100000, m≤ 500000
输入样例：
5 5
1 2
2 3
1 3
3 4
4 5
输出样例：
8
8
16
14
8
#include
using namespace std;
#define N 100005
#define M 500005
int n, m;
int head[N], tot, ver[M*2], nxt[M*2];
int dfn[N], low[N], sz[N], num;
bool cut[N];
long long ans[N];
inline void add(int x, int y)
{
ver[++tot] = y;
nxt[tot] = head[x];
head[x] = tot;
}
void tarjan(int x, int in_edge)
{
dfn[x] = low[x] = ++num; //dfn与low都需要进行初始化
sz[x] = 1;//先初始化为1，然后随着进行，不断累积加
int flag = 0;
long long sum = 0;//表示所有满足low[y]>=dfn[x]的情况下
//size(y)*(n-size(y))的和
long long sum_s = 0;//表示所有满足low[y]>=dfn[x]的情况下
//size(y)的和
for(int i = head[x]; i; i = nxt[i])
{
int y = ver[i];
if(!dfn[y])
{
tarjan(y, i);
sz[x] += sz[y];
low[x] = min(low[x], low[y]);
if(low[y] >= dfn[x])
{
flag++;
if(flag > 1 || dfn[x] > 1)
cut[x] = true;
sum += (long long)sz[y] * (n - sz[y]);//涉及到里那个高int进行乘法，一定要转化为longlong
sum_s += sz[y];
}
}
else if((in_edge^1) != i)
{
low[x] = min(low[x], dfn[y]);
}
}
if(cut[x]) ans[x] = sum + (n-1) + (long long)(n-1-sum_s)*(sum_s+1);// 注意：假设x是root的时候，同样成立
//因为(long long)(n-1-sum_s)*(sum_s+1)为0
else ans[x] = 2*(n-1);
}
int main()
{
tot = 1;
scanf("%d%d", &n, &m);
for(int i = 1; i
无向图的双连通分量
定义
对于无向图：
点双连通图：没有割点的图。
边双连通图：没有割边的图。
点双连通子图：没有割点的子图。
边双连通子图：没有割边的子图。
点双连通分量（v-DDC）：极大的没有割点的子图。
边双连通分量（e-DDC）极大的没有割边的子图。（注意：一个点可能在多个分量中）
定理
点双连通图的充分必要条件
-
图中的顶点数目不超过2.
-
图中的任意两个点同时被包含在一个简单环中。
“8”不算简单环，上面的部分以及下面的部分是简单环。
充分性
对于1，易证
对于2，除去删除的这一个点之外，由于任意两个点都在环中，即有两条独立的路径，删除一个点之后，并没有什么大碍。
必要性
对于1，容易
对于2，
使用反证法：假设有一幅图是点双连通分量，但是有两个点不在一个简单环中。
边双连通图的充分必要条件
任意一条边都至少被包含到一个简单环中
充分性
由于在环中，边两端的端点是还有其他路径，所以删除这一条边并不会影响连通性。
必要性
反证法：假设边双连通图的某一条边不在任意一个简单环中，那么删除这一条边，图不在连通，那么不是边双连通图。如果图连通，那么与 不在任意一个简单环中矛盾。
边双连通分量的求法
如果要是按照寻找环的方法来做，有点离谱。
由定义知：边双连通分量一定没有割边。所以把原图的割边全部去除，就是边双连通子图，由于增加任意一条边，就不再是边双连通子图，所以满足 极大，所以，使用tarjan找到割边，然后去除割边就可以了。
算法实现
int bridge[N];
int c[N], ddc;
void dfs(int x)
{
c[x] = ddc;
for(int i = head[x]; i; i = nxt[i])
{
int y = ver[i];
if(!c[y] && !bridge[i])
{
dfs(y);
}
}
}
//main()
tarjan(1, 0);
for(int i = 1; i
边双连通分量的缩点
方法：使用 c[]数组中的值进行取代原来的边连通分量，建立一张新的图。
int hc[N], vc[M * 2], nc[M * 2], tc;
inline void add_c(int x, int y)
{
vc[++tc] = y;
nc[tc] = hc[x];
hc[x] = tc;
}
// main()
tc = 1;
for (int i = 2; i
点双连通分量的求法
注意，点双连通分量不可以删除割点。
#include
using namespace std;
#define N 305
int n, m;
int dfn[N], num, low[N];
vector ddc[N];
int cnt; //针对ddc的组数。
bool cut[N];
int stac[N], top;
int head[N], tot, nxt[N], ver[N];
void tarjan(int x, int in_edge)
{
stac[++top] = x;
int flag = 0;
dfn[x] = low[x] = ++num;
if (x == 1 && head[x] == 0) //孤立点的情况
{
++cnt;
ddc[cnt].push_back(x);
return;
}
for (int i = head[x]; i; i = nxt[i])
{
int y = ver[i];
if (!dfn[y])
{
tarjan(y, i);
low[x] = min(low[x], low[y]);
if (low[y] >= dfn[x])
{
flag++;
if (flag > 1 || dfn[x] > 1)//dfn[x] > 1就表示不是根节点
cut[x] = true;
cnt++;
int z;
do
{
z = stac[top--];
ddc[cnt].push_back(z);
} while (z != y);
ddc[cnt].push_back(x);
}
}
else if ((in_edge ^ 1) != i)
low[x] = min(low[x], dfn[y]);
}
}
int main()
{
tarjan(1, 0); //其实可以不用存储fa，因为如果有重边，在更新过程中，最多也只是更新到fa，但是
//在割点中看的是小于等于，所以并不影响。
for (int i = 1; i
点双连通分量的缩点
由于割点可能会出现在两个甚至多个分量中，所以并不是原图意义上的缩点
Original: https://www.cnblogs.com/xjsc01/p/16609084.html
Author: 心坚石穿
Title: 算法竞赛进阶指南 0x66 Tarjan 算法与无向图连通性
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/605217/
转载文章受原作者版权保护。转载请注明原作者出处！