图的连通性：DFS 树、割点与桥、双连通分量

DFS 树

DFS 树即深度优先生成树。

从一个点开始对有向图做 DFS 后可以得到一棵 DFS 树，树上的边就称为树边。

从一个点指向其子树中的点的边称为前向边。
从一个点指向其祖先的边称为后向边（返祖边）。
若边的两端点位于它们的 LCA 的两个不同子树中，那么这条边是一条横叉边。横叉边满足起点被遍历到的时间晚于终点（否则这条边会变成树边）。

在无向图中，只有树边和返祖边（不区分前向边和后向边）

定义

割点（割顶）

在一个无向图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点集合。

如果某个割点集合只含有一个顶点 $X$ （也即 $\{X\}$ 是一个割点集合），那么 $X$ 称为一个割点（割顶）。

割边（桥）

在一个无向图中，若删去某条边后无向图的连通分量增加，则称这条边为这张图的割边（桥）。

判定

前置算法：Tarjan 算法。

割点的判定

在 DFS 树中，如果以某个点为根的子树中没有向外（不包括根的父节点）的边（返祖边），那么它的父节点就是一个割点。在算法中表现为 dfn[u]<=low[v] （注意：可以取等）。

如下图：

特别注意：当根节点只有一个子树时，根节点不是割点。

割边的判定

在 DFS 树中，如果以某个点为根的子树中没有向外的边（返祖边），那么从它到它的父节点的边就是一条割边。在算法中表现为 dfn[u]<low[v] （注意：不能取等）。

例题：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

//洛谷 P2860 [USACO06JAN]冗余路径Redundant Paths 

int read()
{
	int x=0;
	bool f=false;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
			f=true;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f?-x:x;
}

struct edge{
	int to,next,op;
}a[20010];

int dfn[5005],low[5005];
int stack[5005],con[5005];
int belong[5005],first[5005];
bool bridge[20010];
int n,m,tot,top,bcc,ans,cnt;

void add(int x,int y)
{
	tot++;
	a[tot].to=y;
	a[tot].next=first[x];
	first[x]=tot;
	a[tot].op=tot+1;
	
	tot++;
	a[tot].to=x;
	a[tot].next=first[y];
	first[y]=tot;
	a[tot].op=tot-1;
}

void dfs(int x,int in)
{
	int y;
	low[x]=dfn[x]=++cnt;
	stack[++top]=x;
	for(int i=first[x];i;i=a[i].next)
	{
		if(i==a[in].op)
			continue;
		y=a[i].to;
		if(!dfn[y])
		{
			dfs(y,i);
			low[x]=min(low[x],low[y]);
			if(low[y]>dfn[x])
				bridge[i]=bridge[a[i].op]=true;
		}
		else
			low[x]=min(low[x],dfn[y]);
	}
	if(low[x]==dfn[x])
	{
		int i;
		bcc++;
		do
		{
			i=stack[top--];
			belong[i]=bcc;
		}while(i!=x);
	}
}

int main()
{
	n=read();
	m=read();
	for(int i=1;i<=m;i++)
		add(read(),read());
	dfs(1,0);
	for(int i=1;i<=n;i++)
		for(int k=first[i];k;k=a[k].next)
			if(bridge[k])
				con[belong[i]]++;
	for(int i=1;i<=bcc;i++)
		if(con[i]==1)
			ans++;
	printf("%d\n",(ans+1)/2);
	return 0;
}

注：部分资料来源于百度百科

双连通分量

双连通分量又分点双连通分量和边双连通分量两种。

若一个无向图中的去掉任意一个节点（一条边）都不会改变此图的连通性，即不存在割点（桥），则称作点（边）双连通图。

一个无向图中的每一个极大点（边）双连通子图称作此无向图的点（边）双连通分量。

求双连通分量可用 Tarjan 算法。

点双连通分量

若一个无向图中的去掉任意一个节点都不会改变此图的连通性，即不存在割点，则称作点双连通图。

一个无向图中的每一个极大点双连通子图称作此无向图的点双连通分量。

注意：一个割点属于多个点双连通分量。

代码实现：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5005;
const int MAXM = 10005;

struct Edge
{
	int to, nxt;
};
Edge e[2 * MAXM + 5];
int head[MAXN], ecnt = 1;
int dfn[MAXN], low[MAXN], timer;

int stk[2 * MAXM], top;   // 边栈
int vbcc;                 // 点双个数
int mark[MAXN];
vector<int> member[MAXN];

void addEdge(int u, int v)
{
	e[++ecnt] = {v, head[u]};
	head[u] = ecnt;
	e[++ecnt] = {u, head[v]};
	head[v] = ecnt;
}

void tarjan(int u, int inEdge)
{
	dfn[u] = low[u] = ++timer;
	for (int i = head[u]; i; i = e[i].nxt)
	{
		if (i == (inEdge ^ 1))
			continue;
		int v = e[i].to;
		if (!dfn[v])
		{
			stk[++top] = i;
			tarjan(v, i);
			low[u] = min(low[u], low[v]);
			if (low[v] >= dfn[u])
			{
				++vbcc;
				int id;
				do
				{
					id = stk[top--];
					int x = e[id].to, y = e[id ^ 1].to;
					if (mark[x] != vbcc)
					{
						mark[x] = vbcc;
						member[vbcc].push_back(x);
					}
					if (mark[y] != vbcc)
					{
						mark[y] = vbcc;
						member[vbcc].push_back(y);
					}
				} while (id != i);
			}
		}
		else if (dfn[v] < dfn[u])
		{
			stk[++top] = i;
			low[u] = min(low[u], dfn[v]);
		}
	}
}

int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; ++i)
	{
		int u, v;
		scanf("%d %d", &u, &v);
		addEdge(u, v);
	}
	for (int i = 1; i <= n; ++i)
		if (!dfn[i])
			tarjan(i, 0);
	for (int i = 1; i <= n; ++i) // 孤立点单独算一个
		if (head[i] == 0)
		{
			++vbcc;
			member[vbcc].push_back(i);
		}
	printf("%d\n", vbcc);
	for (int i = 1; i <= vbcc; ++i)
	{
		for (int x : member[i])
			printf("%d ", x);
		printf("\n");
	}
	return 0;
}

边双连通分量

若一个无向图中的去掉任意一条边都不会改变此图的连通性，即不存在桥，则称作边双连通图。

一个无向图中的每一个极大边双连通子图称作此无向图的边双连通分量。

连接两个边双连通分量的边即是桥。