图论

算法竞赛图相关知识

二分图判定

定义: 可以划分成两个子集,子集内部没有边方法: 直接用 BFS 广搜

连通性

割边割点

割边: 删除这条边,图不连通割点: 删除这个顶点和这个顶点的边,图不连通

Tarjan

[!TIP]
我对于 low 的理解就是,当前节点不通过反向边到达的最小的 num节点是什么两个重要的维护信息:
1.dfs_num(u): DFS 第一次访问顶点 u 的时间
2.dfs_low(u): 表 示 u 在 DFS 子树中能达到的最小 dfs_num 值

判断 割点:

1. 若 u 的子节点是 v,且满足 dfs_low(v) >= dfs_num(u) -> u 是割点(根节点需要特判)

判断 割边:

1. 若 u 的子节点是 v,且满足 dfs_low(v) > dfs_num(u) -> (u -> v) 是割边(根节点需要特判)

[!TIP]
首先我们要明白一个很重要的性质,就是为什么 dfs_low 和 dfs_num 可以判断 割点和割边的存在,dfs_
low,dfs_num到底是表达了什么

vector g(n + 1,vector<int>());
vector<int> dfs_num(n + 1, 0), dfs_low(n + 1, 0), dfs_f(n + 1, 0);
vector<bool> vec(n + 1, 0); //割点判断
vector<array<int,2>> vec2; //割边
int id = 0;
int root, ch; // 针对于 根节点的判断

auto dfs = [&](auto &&dfs, int u) -> void{
	dfs_num[u] = dfs_low[u] = ++id;
	for(auto v : g[u]){
		if(!dfs_num[v]){
			if(u == root) ch++;
			dfs_f[v] = u;
			 dfs(v);
			 if(dfs_low[v] >= dfs_num[u]) vec[u] = 1;
			 if(dfs_low[v] > dfs_num[u]) vec2.push_back(u, v);
			 dfs_low[u] = min(dfs_low[u], dfs_low[v]);
		}else if(v != dfs_f[u]){
			dfs_low[u] = min(dfs_num[v], dfs_low[u]);
		}
	}
};

强连通分量(SCC)

Kosaraju 算法

为什么要使用转置图?

因为你将每一个强连通分量想成一个大顶点,根据在原图上的 DFS 我一定是从 1(强连通分量) -> 2(强连通分量) -> 3(强连通分量),使用转置图,相当于 图的节点变成了 1(强连通分量) <- 2(强连通分量) <- 3(强连通分量),在这个基础上我根据 DFS 的顺序访问,我会先访问 强连通分量1,再2后3.(天才想法💡)

1. 首先通过 DFS 得到节点的访问顺序

2. 在转置图中,从访问顺序还是访问(对每一个未访问过的顶点进行DFS,直到访问玩所有节点):每一次DFS都是访问一个强连通分量

vector g1(n + 1, vector<int>());
vector g2(n + 1, vector<int>());

Tarjan 算法

也是借用 dfs_num 和 dfs_low 来求强连通分量

dfs_num == dfs_low 进行弹栈操作

vector<int> num(n + 1, 0), low(n + 1, 0);
vector g(n + 1, vector<int>());
vector<bool> vis(n + 1, 0); stack<int>exp;
int id = 0;
int SCC = 0;
auto Tarjan = [&](auto &&Tarjan, int u) -> void{
	vis[u] = 1; exp.push(u);
	num[u] = low[u] = ++id;
	for(auto v : g[u]){
		if(!num[v]) Tarjan(v);
		if(vis[v]) low[u] = min(low[u], num[v]);
	}
	if(num[u] == low[u]){
		SCC++;
		int v;
		// 这个里面就是一个强连通分量
		while(1){
			v = exp.top(); exp.pop();
			vis[v] = 0;
			if(v == u) break;
		}
	}
};