连通性

图论中的连通性相关的算法
(适合学过之后，总结复习的观看)
割边，割点，缩点

其实都有个共同的名字：tarjan

割边

对于一个连通的无向图，如果存在一条边，去除后，使其分为两个子图，无法连通，那么这个边可以称为割边

例题 炸铁路

对于一个访问过的点，且不是父节点\(low[u]=min(low[u],dfn[v])\)
对于一个未访问的点，\(low[u]=min(low[v],low[u])\)
判断割边的条件\(low[v]>dfn[u]\),则满足\((u,v)\)是一个割边

#include<bits/stdc++.h>

using namespace std;
int n,m;
const int maxn=1e4+10;
struct node {
	int v,next;
}e[maxn];
int head[maxn];
int cnt=0;
void add(int u,int v){
	e[++cnt].v=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}
vector<pair<int,int> >ans;
int tot=0;
int f[maxn]; 
int dfn[maxn],low[maxn];

void tarjan(int u,int fa){
	dfn[u]=low[u]=++tot;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].v;
		if(v!=fa && dfn[v])
			low[u]=min(low[u],dfn[v]);
		if(!dfn[v]){
			tarjan(v,u);
			low[u]=min(low[v],low[u]);
			if(low[v]>dfn[u]) ans.push_back({min(u,v),max(u,v)}); 
		}
	}
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		int a,b;cin>>a>>b;
		add(a,b);add(b,a);
	}
	for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i,i);
	sort(ans.begin(),ans.end());
	for(auto x:ans) cout<<x.first<<" "<<x.second<<endl;
	return 0;
} 

割点

例题 P3388 【模板】割点（割顶）

对于一个访问的点\(low[u]=min(low[u],dfn[v]);\)
对于一个未访问的点\(u!=fa,low[v]>=dfn[u]\)，则u是割点
特别考虑开始遍历的根节点，如果有两颗以上的子树，则一定是割点

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;
int n,m;
const int maxn=1e5+10;
int head[maxn],low[maxn],dfn[maxn];
struct node{
	int v,next;
}e[maxn<<1];
bool book[maxn];
int cnt=0,tot=0;
void add(int u,int v){
	e[++cnt].v=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}
void dfs(int u,int fa){
	low[u]=dfn[u]=++tot;
	int child=0;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].v;
		if(!dfn[v]){
			dfs(v,fa);
			low[u]=min(low[u],low[v]);
			if(u!=fa && low[v]>=dfn[u]) book[u]=1;
			if(u==fa) ++child;
		}
		else if(book[v])low[u]=min(low[u],dfn[v]);
	}
	if(u==fa && child>=2) book[u]=1;
}
int main(){
	cin>>n>>m;memset(book,0,sizeof(book));
 	for(int i=1;i<=m;++i){
		int u,v;cin>>u>>v;
		add(u,v);add(v,u); 
	}
	int js=0;
	for(int i=1;i<=n;++i) if(!dfn[i]) dfs(i,i);
	for(int i=1;i<=n;++i) if(book[i]) ++js;
	cout<<js<<endl;
	for(int i=1;i<=n;++i) if(book[i]) cout<<i<<" ";
	return 0; 	
}

缩点

对于一个有向图形成的环，我们可以将其压缩成一个点

P3387 【模板】缩点

缩点+拓扑排序

对于一个点，无论是否访问过，\(low[u]=min(low[u],low[v])\)

这里模板特别加上了拓扑排序，我们可以学会对缩点进行重新编号再操作

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;

const int maxn=1e5+10;
int p[maxn];
int n,m;
int dfn[maxn],low[maxn];
int top=0;
bool vl[maxn];
int st[maxn],sd[maxn];
int sum=0,cnt=0;
int head[maxn*20];
struct node{
	int next,v,u; 
}e[maxn*20],a[maxn*20];
void add(int u,int v){
	e[++cnt].v=v;
	e[cnt].u=u;
	e[cnt].next=head[u];
	head[u]=cnt;
}
void dfs(int u){
	low[u]=dfn[u]=++sum;
	st[++top]=u;vl[u]=1;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].v;
		if(!dfn[v]){
			dfs(v);
			low[u]=min(low[u],low[v]);
		}
		else if(vl[v]) low[u]=min(low[u],low[v]);
	}
	if(dfn[u]==low[u]){//强连通分量的根节点 
		int x;
		while(x=st[top--]){
			sd[x]=u;//缩点 
			vl[x]=0;//使该点在之后不再能被访问
			if(x==u) break;
			p[u]+=p[x];
		}
	}
	return ;
}
void tarjan(){
	memset(vl,0,sizeof(vl));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	for(int i=1;i<=n;++i) 
		if(!dfn[i]) dfs(i);
}
int ct=0,r[maxn];
int h[maxn*20];
void topsort(){
	queue<int>q;
	int dis[maxn];
	memset(dis,0,sizeof(dis));
	for(int i=1;i<=n;++i)
		if(sd[i]==i && !r[i])
			q.push(i),dis[i]=p[i];
	while(!q.empty()){
		int k=q.front();q.pop();
		for(int i=h[k];i;i=a[i].next){
			int v=a[i].v;
			dis[v]=max(dis[v],dis[k]+p[v]);
			r[v]--;
			if(!r[v]) q.push(v); 
		} 
	}
	long long ans=0;
	for(int i=1;i<=n;++i)
		if(ans<dis[i]) ans=dis[i];
	cout<<ans<<endl;
	return ;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i) cin>>p[i];
	for(int i=1;i<=m;++i){
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
	tarjan();
	memset(h,0,sizeof(h));
	memset(r,0,sizeof(r));
	for(int i=1;i<=m;++i){
		int u=sd[e[i].u],v=sd[e[i].v];
		if(u!=v){
			a[++ct].next=h[u];
			a[ct].v=v;
			a[ct].u=u;
			h[u]=ct;
			++r[v];
		}
	}
	topsort();
	return 0;
} 

总结

我们通过这三个算法，可以进行一定的区分和寻找一定的相似的地方

区分

判定条件

访问点

这里应该是最不好理解的一点，我给出一种解释希望有所帮助：

low[u]表示的是节点u能够通过回边或子树到达的最小的节点编号

回边的存在：当我们在DFS中访问节点u的邻接节点v时，如果v已经被访问且在当前的递归栈中（即 in_stack[v] 为真），这意味着存在一条回边从 u到v。这条回边表明u可以通过v回到某个更早的节点。

dfn[v]是节点v被访问时的时间戳，表示v在DFS中的访问顺序。通过比较low[u]和dfn[v]，我们可以确定u能够到达的最小节点编号。如果v的时间戳小于low[u]，这意味着u可以通过v到达一个更早的节点，因此我们需要更新low[u]

相似点

都通过比较low和dfn的大小来确定是否存在割点，割边，缩边