图论 - 连通性问题 - 洛谷保存站

# 强连通问题

1. 有向图的强连通：有向图的两个点 $x,y$ 彼此能够到达，称 $x$ 和 $y$ 强连通。
2. 强联通分量 $\text{(Strongly Connected Components,SCC)}$：表示有向图的一个极大子图 $G$，满足 $G$ 的任意两点都是强连通的。
	+ 特殊情况：
		* 单点算 $1$ 个 $\text{SCC}$；
		* 有向图最少有 $1$ 个 $\text{SCC}$，最多有 $n$ 个；
		* $\text{SCC}$ 要么是一个单点，要么是一个环；
		* $\text{SCC}$ 不一定是一个简单环。
3. 强连通分量的判定 $\text{(Tarjan)}$：
	+ 概念：
		* $dfn_x$ 表示在一个 $\text{dfs}$ 序中的时间戳；
		* $low_x$ 表示在一个 $\text{dfs}$ 序中从 $x$ 出发能够到达的点的最小时间戳。
	+ 策略：
		* 寻找进入一个环的时间戳最早的点；
		* 越晚搜到的点越早确定 $\text{SCC}$，所以需要栈。
		* 找到一个“关键点”，则栈顶到关键点之间的所有点在同一个 $\text{SCC}$ 内。
			- 关键点指 $dfn_x=low_x$ 的点。

## 例题：[P3119](/problem/P3119)

### 分析：

1. 如果不反边，先 $\text{Tarjan}$ 缩点，每个点设点权，建新图；
2. 从原图点 $1$ 所在的 $\text{SCC}$ 开始跑最长路；
3. 如果不反边，答案就是 $size_{scc_1}$；
4. 如果反边，显而易见的，反边一定在两个 $\text{SCC}$ 之间，答案计算显然。

### 代码：

```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,stk[100005],cnt,ans,low[100005],dfn[100005],top,cntscc,scc[100005],dis1[100005],dis2[100005],siz[100005];
bool vis[100005];
vector<int>e[100005],g[100005],h[100005];
queue<int>q;
void tarjan(int cur){
	dfn[cur]=low[cur]=++cnt,stk[++top]=cur,vis[cur]=1;
	for(int x:e[cur]){
		if(!dfn[x]){
			tarjan(x);
			low[cur]=min(low[cur],low[x]);
		}
		else if(vis[x])
			low[cur]=min(low[cur],dfn[x]);
	}
	if(dfn[cur]==low[cur]){
		cntscc++;
		int x;
		do
			x=stk[top--],scc[x]=cntscc,vis[x]=0,siz[cntscc]++;
		while(cur!=x);
	}
}
void spfa(vector<int>e[],int dis[]){
	q.emplace(scc[1]);
	vis[scc[1]]=1,dis[scc[1]]=siz[scc[1]];
	while(!q.empty()){
		int cur=q.front();
		q.pop();
		vis[cur]=0;
		for(int x:e[cur]){
			if(dis[cur]+siz[x]<=dis[x])
				continue;
			dis[x]=dis[cur]+siz[x];
			if(!vis[x]){
				q.emplace(x);
				vis[x]=1;
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1,u,v;i<=m;i++){
		cin>>u>>v;
		e[u].emplace_back(v);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i);
	for(int i=1;i<=n;i++)
		for(int x:e[i])
			if(scc[i]!=scc[x]){
				g[scc[i]].emplace_back(scc[x]);
				h[scc[x]].emplace_back(scc[i]);
			}
	n=cntscc;
	spfa(g,dis1);
	spfa(h,dis2);
	ans=siz[scc[1]];
	for(int i=1;i<=n;i++)
		for(int x:h[i])
			if(dis1[i]&&dis2[x])
				ans=max(ans,dis1[i]+dis2[x]-siz[scc[1]]);
	cout<<ans;
	return 0;
}
```

# 双连通问题

1. 割点：在一张无向图中，若删除点 $x$ 能使得连通块数量增多，那么称 $x$ 为割点。
	- 至少有 $3$ 个点的无向图才可能有割点。
2. 割边（桥）：在一张无向图中，若删除一条边 $x-y$ 能使连通块数量增多，那么称边 $x-y$ 为割边。
	- 至少有 $2$ 个点的无向图才可能有割边。
3. [割点的判定](/problem/P3388)：如果存在一条边 $x-y$，使得 $low_y \ge dfn_x$，且 $x$ 不是搜索树的根节点或不止一个子节点，则 $x$ 为割点。
4. [割边的判定](/problem/T103481)：如果存在一条边 $x-y$，使得 $low_y>dfn_x$，则边 $x-y$ 为割边。
5. 点双连通：若无向图中两点 $x,y$ 满足删除除 $x,y$ 以外任意一点仍然满足 $x,y$ 联通，则称点 $x$ 和点 $y$ 是点双连通的。
	- 注：任意一点与自身总是点双连通的，一条边的两端点总是点双连通的。
6. 边双连通：若无向图中两点 $x,y$ 满足删除图中任意一边仍然满足 $x,y$ 联通，则称点 $x$ 和点 $y$ 是边双连通的。
	- 注：任意一点与自身总是边双联通的，但一条边的两端点不一定是边双连通的。
7. 双连通的传递性：点双连通不具有传递性，边双连通具有传递性。
8. 点双连通分量 $\text{(V-DCC)}$：在无向图中，若一个极大子图 $G$ 满足该图中没有割点，则称该图是一个点双连通分量。
9. 边双连通分量 $\text{(E-DCC)}$：在无向图中，若一个极大子图 $G$ 满足该图中没有割边，则称该图是一个边双连通分量。
10. 点双连通分量和边双连通分量都是为了处理环，二者缩点后均为森林。
11. 点双连通分量与边双连通分量的性质：
	- 一个点至多在一个边双连通分量中，但可以在多个点双连通分量中；
	- 一个点是割点当且仅当该点在多个点双连通分量中；
	- 两个边双连通分量没有交点，两个点双连通分量至多有一个交点；
	- 无向图上两点 $x,y$ 之间任意一条路径上的割边即为点 $x$ 到点 $y$ 的所有路径的必经边。

## 例题：[CF521E](/problem/CF521E)

[$\text{Solution}$](https://www.luogu.com.cn/blog/529697/solution-cf521e)

正在渲染内容...