08.18总结

连通分量

连通分量是指图中满足连通条件的极大子图，也称为连通块。所谓子图，就是从原图中选取部分顶点和边所构成的图。连通子图需要满足其中任意两个顶点之间都存在路径相连。而极大连通子图则要求在保证连通性的前提下，尽可能包含更多的顶点和边。需要注意的是，这里的"极大"强调的是无法再扩展的局部最大性，而非全局意义上的 “最大”。

割点

割点是图论中的关键概念，其定义为：在无向连通图中，若删除某顶点及其邻接边会导致图分裂为多个连通分量，则该顶点称为割点。割点揭示了图的连通性对特定顶点的依赖关系，移除这些关键顶点将破坏图的整体连通性。若采用暴力枚举法，即依次删除每个顶点并计算连通分量数量，时间复杂度将达到 $O(nm)$。因此，实际应用中通常采用下文中会提到的效率更高的 tarjan 算法来识别割点。

tarjan

该算法采用深度优先搜索（dfs）框架，利用节点访问时间戳和回溯值来识别割点。它用时间戳（dfn）标记节点在 dfs 遍历中的访问顺序，回溯值（low）是在不经过（搜索树中）父节点的情况下能到达的最小的节点 dfs 序。割点的判定标准：如果它是根节点，当且仅当拥有两棵及以上子树时判定为割点。否则，若它存在子节点 $v$ 满足 $lo{w}_v⩾df{n}_u$，则该节点 $u$ 为割点。时间复杂度为 $O(n+m)$（$n$ 为节点数，$m$ 为边数），空间复杂度为 $O(n)$。

实现

以 Luogu P3388 为例

#include<bits/stdc++.h>
using namespace std;
vector <int> ve[100001];
int n, m, r, dfn[100001], low[100001], l, root[100001];
int ans[10000001];
void dfs(int u, int fa){
    int scn = 0;//u 的 儿子数
    l++;
    dfn[u] = low[u] = l;//dfs 序
    int flag = 0;
    for (auto v : ve[u]){
        if(dfn[v]){
            low[u] = min(low[u], dfn[v]);//比较 v 的 编号是不是比 u 小（因为 u 可达 v）
        } else {
            dfs(v, u);
            scn++;//找到一个儿子
            low[u] = min(low[u], low[v]);
            if(!flag && u != fa && low[v] >= dfn[u]){
                ans[u] = 1;
                r++;
                flag = 1;
            }
        }
    } 
    if(!flag && u == fa && scn > 1){//记得根节点特判
        r++;
        ans[u] = 1;
    }
}
int main(){
    cin >> n >> m;
    while(m--){
        int x, y;
        cin >> x >> y;
        ve[x].push_back(y);
        ve[y].push_back(x);//建图
        root[y]++;
    }
    for(int i = 1;i <= n;i++){
        if(!root[i]){
            dfs(i, i); 
        }
        
    }
    cout << r << endl;
    for(int i = 1;i <= n;i++){
        if(ans[i]){
            cout << i << ' ';
        }
    }
}

割边

割边（又称桥）与割点的定义相似：删除一条割边后，图中的连通分量会增加。
在没有重边的情况下，只需将割点判定条件中的 $lo{w}_v⩾df{n}_u$ 改为 $lo{w}_v>df{n}_u$ 即可，因为割点基于点，而割边基于边，且 $low$ 和 $dfn$ 记录的都是顶点的时间戳。
若存在重边，这些重边一定不是桥。而割边常见的实现方法有两种：

1. 记录从父节点搜到当前节点的边编号，避免通过该边返回父节点，但仍允许通过其他边访问。
2. 使用标记判断是否存在多条边指向父节点，仅在第二次访问父节点时进行正常处理。

实现

以 Luogu P1656 为例

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector <int> ve[100001];
int n, m, l, r, dfn[100001], low[100001];
pair <int, int> ans[10000001];
void dfs(int u, int fa){
    dfn[u] = low[u] = ++l;
    for (auto v : ve[u]){
        if(v == fa){ //找到它父亲了
            continue;//返祖，不找了
        }
        if(dfn[v]){//如果 v 的 dfn 已经求出来了
            low[u] = min(low[u], dfn[v]);//比较 v 的 编号是不是比 u 小（因为 u 可达 v）
        } else {
            dfs(v, u);//dfs 去找
            low[u] = min(low[u], low[v]);
            if(low[v] > dfn[u]){
                r++;
                ans[r] = {u, v};//结果 pair 入 ans
            }
        }
    } 
}
signed main(){
    cin >> n >> m;
    while(m--){
        int x, y;
        cin >> x >> y;
        ve[x].push_back(y);//建图
        ve[y].push_back(x);
    }
    for(int i = 1;i <= n;i++){
        if(!dfn[i]){
            dfs(i, i); 
        }
    }
    sort(ans + 1, ans + r + 1); //sort 会自动对 pair 的关键字升序排序
    for(int i = 1;i <= r;i++){
        cout << ans[i].first << ' ' << ans[i].second << endl;
    }
}

点双连通分量

点双连通分量（简称点双）是指在图中删除任意一个顶点后仍保持连通的子图。点双具有以下性质：

1. 任意两个点双之间最多存在一个公共顶点，且该顶点必为割点；
2. 在深度优先搜索树中，每个点双的最小dfn值对应的顶点要么是割点，要么是根节点。
   算法实现时，我们使用栈来记录已访问的顶点。当回溯到割点时，将从该割点开始的所有栈顶顶点弹出，构成一个点双连通分量。

实现

以 Luogu P8435 为例

#include <bits/stdc++.h>
using namespace std;
int cnt = 1, fir[500001], nxt[4000001], to[4000001], s[4000001], top, bcc, low[500001], dfn[500001], idx, n, m;
vector<int> ans[500001];
void dfs(int u, int fa) {
	int son = 0;
	idx++;
	top++;
	low[u] = dfn[u] = idx;
	s[top] = u;
	for(int i = fir[u]; i; i = nxt[i]) {
		int v = to[i];
		if(!dfn[v]) {
			son++;
			dfs(v, u);
			low[u] = min(low[u], low[v]);
			if(low[v] >= dfn[u]) {
				bcc++;
				while(s[top + 1] != v) {
                    ans[bcc].push_back(s[top--]);
				}
				ans[bcc].push_back(u);
			}
		} else {
            if(v != fa) {
                low[u] = min(low[u], dfn[v]);
            } 
		}
	}
	if(!fa && !son) {
        ans[++bcc].push_back(u);
	}
}
void ppp(int u, int v) {
	to[++cnt] = v;
	nxt[cnt] = fir[u];
	fir[u] = cnt;
}
int main() {
	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		ppp(u, v);
        ppp(v, u);
	}
	for(int i = 1; i <= n; i++) {
		if(dfn[i]) {
            continue;
		}
		top = 0;
		dfs(i, 0);
	}
	cout << bcc << endl;
	for(int i = 1; i <= bcc; i++) {
		cout << ans[i].size() << ' ';
		for(int j : ans[i]) {
            cout << j << ' ';
	    }
		cout << endl;
	}
	return 0;
}