CVBB ACM Team

用户工具

站点工具

您在这里: front_page » 2020-2021 » teams » legal_string » jxm2001 » 图论_1
2020-2021:teams:legal_string:jxm2001:图论_1

这是本文档旧的修订版！

目录

图论 1

最短路

非负权边单源最短路

$\text{Dijkstra}$ 算法板子

时间复杂度 $O(m\log m)$。 

template <typename T>
struct dijkstra{
	T dis[MAXN];
	bool vis[MAXN];
	priority_queue<pair<T,int>,vector<pair<T,int> >,greater<pair<T,int> > >q;
	void solve(int src,int n){
		mem(vis,0);
		_rep(i,1,n)
		dis[i]=Inf;
		dis[src]=0;
		q.push(make_pair(dis[src],src));
		while(!q.empty()){
			pair<T,int> temp=q.top();q.pop();
			int u=temp.second;
			if(vis[u])
			continue;
			vis[u]=true;
			for(int i=head[u];i;i=edge[i].next){
				int v=edge[i].to;
				if(dis[v]>edge[i].w+dis[u]){
					dis[v]=edge[i].w+dis[u];
					q.push(make_pair(dis[v],v));
				}
			}
		}
	}
};

例题

洛谷p1462

题意

给定 $n$ 个城市，$m$ 条边以及起点、终点。

要求选择一条路径，满足路径边权和不超过给定值，且路径上的最大点权最小。

题解

二分点权上界，跑 $\text{dijkstra}$ 时跳过点权大于该上界的点，计算起点到终点的边权和最短路，如果不超过给定值则更新答案。

时间复杂度 $O(n\log m\log v)$

查看代码

查看代码 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cctype>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <cassert>
#define _for(i,a,b) for(int i=(a);i<(b);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
inline int read_int(){
	int t=0;bool sign=false;char c=getchar();
	while(!isdigit(c)){sign|=c=='-';c=getchar();}
	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
	return sign?-t:t;
}
inline LL read_LL(){
	LL t=0;bool sign=false;char c=getchar();
	while(!isdigit(c)){sign|=c=='-';c=getchar();}
	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
	return sign?-t:t;
}
inline char get_char(){
	char c=getchar();
	while(c==' '||c=='\n'||c=='\r')c=getchar();
	return c;
}
inline void write(LL x){
	register char c[21],len=0;
	if(!x)return putchar('0'),void();
	if(x<0)x=-x,putchar('-');
	while(x)c[++len]=x%10,x/=10;
	while(len)putchar(c[len--]+48);
}
inline void space(LL x){write(x),putchar(' ');}
inline void enter(LL x){write(x),putchar('\n');}
const int MAXN=1e4+5,MAXM=5e4+5,Inf=2e9;
struct Edge{
	int to,w,next;
}edge[MAXM<<1];
int head[MAXN],edge_cnt,val[MAXN],limit;
void Insert(int u,int v,int w){
	edge[++edge_cnt].next=head[u];
	edge[edge_cnt].to=v;edge[edge_cnt].w=w;
	head[u]=edge_cnt;
}
template <typename T>
struct dijkstra{
	T dis[MAXN];
	bool vis[MAXN];
	priority_queue<pair<T,int>,vector<pair<T,int> >,greater<pair<T,int> > >q;
	void solve(int src,int n){
		mem(vis,0);
		_rep(i,1,n)
		dis[i]=Inf;
		dis[src]=0;
		q.push(make_pair(dis[src],src));
		while(!q.empty()){
			pair<T,int> temp=q.top();q.pop();
			int u=temp.second;
			if(vis[u])
			continue;
			vis[u]=true;
			for(int i=head[u];i;i=edge[i].next){
				int v=edge[i].to;
				if(val[v]>limit)
				continue;
				if(dis[v]>edge[i].w+dis[u]){
					dis[v]=edge[i].w+dis[u];
					q.push(make_pair(dis[v],v));
				}
			}
		}
	}
};
dijkstra<LL> dj;
int main()
{
	int n=read_int(),m=read_int(),b=read_int(),u,v,w,lef=Inf,rig=0;
	_rep(i,1,n){
		val[i]=read_int();
		lef=min(val[i],lef);
		rig=max(val[i],rig);
	}
	while(m--){
		u=read_int(),v=read_int(),w=read_int();
		Insert(u,v,w);
		Insert(v,u,w);
	}
	int mid,ans=-1;
	while(lef<=rig){
		mid=lef+rig>>1;
		limit=mid;
		dj.solve(1,n);
		if(dj.dis[n]<=b){
			ans=mid;
			rig=mid-1;
		}
		else
		lef=mid+1;
	}
	if(ans>=0)
	enter(ans);
	else
	puts("AFK");
	return 0;
}

带负权边单源最短路

$\text{SPFA}$ 算法板子

平均时间复杂度 $O(Km)$，最坏时间复杂度 $O(nm)$。 

template <typename T>
struct SPFA{
	T dis[MAXN];
	int len[MAXN];
	bool inque[MAXN];
	bool solve(int src,int n){
		queue<int>q;
		mem(inque,0);mem(len,0);
		_rep(i,1,n)
		dis[i]=Inf;
		dis[src]=0;len[src]=1;
		q.push(src);
		inque[src]=true;
		while(!q.empty()){
			int u=q.front();q.pop();
			inque[u]=false;
			for(int i=head[u];i;i=edge[i].next){
				int v=edge[i].to;
				if(dis[v]>dis[u]+edge[i].w){
					dis[v]=dis[u]+edge[i].w;
					len[v]=len[u]+1;
					if(len[v]>n)
					return false;
					if(!inque[v]){
						q.push(v);
						inque[v]=true;
					}
				}
			}
		}
		return true;
	}
};

例题

洛谷p5960

题意

解方程 $$ \left \{ \begin{array}{l} x_{a1}-x_{b1}\le y_1\\ x_{a2}-x_{b2}\le y_2\\ \cdots\\ x_{am}-x_{bm}\le y_m \end{array} \right. $$

题解

将 $x_j-x_i\le y$ 移项，得 $x_j\le x_i+y$，发现该式与单源最短路的三角不等式 $\text{dist}_j\le \text{dist}_i+\text{w}_{i\to j}$ 相似。

考虑添加超级源点 $x_0$，$x_0$ 向所有其他点连一条权为 $0$ (事实上边权数值无特殊要求，边权相当于为所有解加上一个初始值)的单向边。

然后跑最短路算法即可，解得 $x_i=\text{dist}_i+k$ 为方程的一组可行解。

查看代码

查看代码 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cctype>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <cassert>
#define _for(i,a,b) for(int i=(a);i<(b);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
inline int read_int(){
	int t=0;bool sign=false;char c=getchar();
	while(!isdigit(c)){sign|=c=='-';c=getchar();}
	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
	return sign?-t:t;
}
inline LL read_LL(){
	LL t=0;bool sign=false;char c=getchar();
	while(!isdigit(c)){sign|=c=='-';c=getchar();}
	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
	return sign?-t:t;
}
inline char get_char(){
	char c=getchar();
	while(c==' '||c=='\n'||c=='\r')c=getchar();
	return c;
}
inline void write(LL x){
	register char c[21],len=0;
	if(!x)return putchar('0'),void();
	if(x<0)x=-x,putchar('-');
	while(x)c[++len]=x%10,x/=10;
	while(len)putchar(c[len--]+48);
}
inline void space(LL x){write(x),putchar(' ');}
inline void enter(LL x){write(x),putchar('\n');}
const int MAXN=1e4+5,MAXM=5e5+5,Inf=1e9;
struct Edge{
	int to,w,next;
}edge[MAXM<<1];
int head[MAXN],edge_cnt;
void Insert(int u,int v,int w){
	edge[++edge_cnt].next=head[u];
	edge[edge_cnt].to=v;edge[edge_cnt].w=w;
	head[u]=edge_cnt;
}
template <typename T>
struct SPFA{
	T dis[MAXN];
	int len[MAXN];
	bool inque[MAXN];
	bool solve(int src,int n){
		queue<int>q;
		mem(inque,0);mem(len,0);
		_rep(i,1,n)
		dis[i]=Inf;
		dis[src]=0;len[src]=1;
		q.push(src);
		inque[src]=true;
		while(!q.empty()){
			int u=q.front();q.pop();
			inque[u]=false;
			for(int i=head[u];i;i=edge[i].next){
				int v=edge[i].to;
				if(dis[v]>dis[u]+edge[i].w){
					dis[v]=dis[u]+edge[i].w;
					len[v]=len[u]+1;
					if(len[v]>n)
					return false;
					if(!inque[v]){
						q.push(v);
						inque[v]=true;
					}
				}
			}
		}
		return true;
	}
};
SPFA<int> spfa;
int main()
{
	int n=read_int(),m=read_int(),u,v,w;
	_rep(i,1,n)Insert(n+1,i,0);
	while(m--){
		u=read_int(),v=read_int(),w=read_int();
		Insert(v,u,w);
	}
	if(spfa.solve(n+1,n+1)){
		_rep(i,1,n){
			if(i>1)putchar(' ');
			write(spfa.dis[i]);
		}
	}
	else
	puts("NO");
	return 0;
}

带负权边全源最短路

$\text{Floyd}$ 算法板子

时间复杂度 $O(n^3)$，无法判断负环。 

int n,dis[MAXN][MAXN];
void Floyd(){
	_for(i,0,n)
	_for(j,0,n)
	dis[i][j]=Inf;
	_for(i,0,n)
	dis[i][i]=0;
	_for(k,0,n)
	_for(i,0,n)
	_for(j,0,n)
	dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}

例题

洛谷p1119

题意

给定 $n$ 个城市，$m$ 条边，每个城市在第 $t_i$ 天起才加入点集(保证 $t_i$ 升序)。

$q$ 个询问，每次询问第 $t$ 天的 $dis(i,j)$，保证询问的 $t$ 升序。

题解

考虑 $\text{Floyd}$ 算法本质其实是 $\text{dp}$。

$dis[k][i][j]$ 表示只使用前 $k$ 个点作为中转点时 $i$、$j$ 间的最短路，可以用滚动数组省去一维。

所以本题只需要按时间更新即可。

查看代码

查看代码 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cctype>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <cassert>
#define _for(i,a,b) for(int i=(a);i<(b);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
inline int read_int(){
	int t=0;bool sign=false;char c=getchar();
	while(!isdigit(c)){sign|=c=='-';c=getchar();}
	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
	return sign?-t:t;
}
inline LL read_LL(){
	LL t=0;bool sign=false;char c=getchar();
	while(!isdigit(c)){sign|=c=='-';c=getchar();}
	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
	return sign?-t:t;
}
inline char get_char(){
	char c=getchar();
	while(c==' '||c=='\n'||c=='\r')c=getchar();
	return c;
}
inline void write(LL x){
	register char c[21],len=0;
	if(!x)return putchar('0'),void();
	if(x<0)x=-x,putchar('-');
	while(x)c[++len]=x%10,x/=10;
	while(len)putchar(c[len--]+48);
}
inline void space(LL x){write(x),putchar(' ');}
inline void enter(LL x){write(x),putchar('\n');}
const int MAXN=200+5,Inf=1e9;
int dis[MAXN][MAXN],t[MAXN];
int main()
{
	int n=read_int(),m=read_int(),u,v,w;
	_for(i,0,n)
	t[i]=read_int();
	_for(i,0,n)
	_for(j,0,n)
	dis[i][j]=Inf;
	while(m--){
		u=read_int(),v=read_int(),w=read_int();
		dis[u][v]=dis[v][u]=w;
	}
	_for(i,0,n)
	dis[i][i]=0;
	int q=read_int(),pos=0,temp;
	while(q--){
		u=read_int(),v=read_int(),temp=read_int();
		while(t[pos]<=temp&&pos<n){
			_for(i,0,n)
			_for(j,0,n)
			dis[i][j]=min(dis[i][j],dis[i][pos]+dis[pos][j]);
			pos++;
		}
		if(t[u]>temp||t[v]>temp||dis[u][v]==Inf)
		enter(-1);
		else
		enter(dis[u][v]);
	}
	return 0;
}

$\text{Johnson}$ 算法板子

洛谷p5905

加入虚拟节点，虚拟节点向每个点连一条权值为 $0$ 的单向边。

跑一遍 $\text{SPFA}$，得到每个点到虚拟节点的距离，记该距离为每个点的势能 $h_i$。

将原图中的所有边权修改 $w+h_u-h_v$，则新图的每条路径 $s\to t$ 的长度为

\begin{equation}(w_{s,p1}+h_s-h_{p1})+(w_{p1,p2}+h_{p1}-h_{p2})+\cdots+(w_{pk,t}+h_{pk}-h_t)=w_{s,p1}+w_{p1,p2}+\cdots+w_{pk,t}+h_s-h_t\end{equation}

所以新图的最短路与原图等效。

另外，根据 $\text{SPFA}$ 结果，有 $h_v\le h_u+w_{u,v}$，即 $w_{u,v}+h_u-h_v\ge 0$。

由于新图所有边权非负，所以可以跑 $n$ 轮 $\text{Dijkstra}$ 求出全源最短路。

时间复杂度 $O(nm\log m)$，带负环判断。

查看代码

查看代码 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cctype>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <cassert>
#define _for(i,a,b) for(int i=(a);i<(b);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
inline int read_int(){
	int t=0;bool sign=false;char c=getchar();
	while(!isdigit(c)){sign|=c=='-';c=getchar();}
	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
	return sign?-t:t;
}
inline LL read_LL(){
	LL t=0;bool sign=false;char c=getchar();
	while(!isdigit(c)){sign|=c=='-';c=getchar();}
	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
	return sign?-t:t;
}
inline char get_char(){
	char c=getchar();
	while(c==' '||c=='\n'||c=='\r')c=getchar();
	return c;
}
inline void write(LL x){
	register char c[21],len=0;
	if(!x)return putchar('0'),void();
	if(x<0)x=-x,putchar('-');
	while(x)c[++len]=x%10,x/=10;
	while(len)putchar(c[len--]+48);
}
inline void space(LL x){write(x),putchar(' ');}
inline void enter(LL x){write(x),putchar('\n');}
const int MAXN=3e3+5,MAXM=9e3+5,Inf=1e9;
struct Edge{
	int to,w,next;
}edge[MAXM];
int head[MAXN],edge_cnt;
void Insert(int u,int v,int w){
	edge[++edge_cnt].next=head[u];
	edge[edge_cnt].to=v;edge[edge_cnt].w=w;
	head[u]=edge_cnt;
}
template <typename T>
struct SPFA{
	T dis[MAXN];
	int len[MAXN];
	bool inque[MAXN];
	bool solve(int src,int n){
		queue<int>q;
		mem(inque,0);mem(len,0);
		_rep(i,1,n)
		dis[i]=Inf;
		dis[src]=0;len[src]=1;
		q.push(src);
		inque[src]=true;
		while(!q.empty()){
			int u=q.front();q.pop();
			inque[u]=false;
			for(int i=head[u];i;i=edge[i].next){
				int v=edge[i].to;
				if(dis[v]>dis[u]+edge[i].w){
					dis[v]=dis[u]+edge[i].w;
					len[v]=len[u]+1;
					if(len[v]>n)
					return false;
					if(!inque[v]){
						q.push(v);
						inque[v]=true;
					}
				}
			}
		}
		return true;
	}
};
template <typename T>
struct dijkstra{
	T dis[MAXN];
	bool vis[MAXN];
	priority_queue<pair<T,int>,vector<pair<T,int> >,greater<pair<T,int> > >q;
	void solve(int src,int n){
		mem(vis,0);
		_rep(i,1,n)
		dis[i]=Inf;
		dis[src]=0;
		q.push(make_pair(dis[src],src));
		while(!q.empty()){
			pair<T,int> temp=q.top();q.pop();
			int u=temp.second;
			if(vis[u])
			continue;
			vis[u]=true;
			for(int i=head[u];i;i=edge[i].next){
				int v=edge[i].to;
				if(dis[v]>edge[i].w+dis[u]){
					dis[v]=edge[i].w+dis[u];
					q.push(make_pair(dis[v],v));
				}
			}
		}
	}
};
SPFA<int> spfa;
dijkstra<int> dj;
int main()
{
	int n=read_int(),m=read_int(),u,v,w;
	_for(i,0,m){
		u=read_int(),v=read_int(),w=read_int();
		Insert(u,v,w);
	}
	_rep(i,1,n)
	Insert(n+1,i,0);
	if(!spfa.solve(n+1,n+1)){
		puts("-1");
		return 0;
	}
	_rep(u,1,n){
		for(int i=head[u];i;i=edge[i].next){
			int v=edge[i].to;
			edge[i].w+=spfa.dis[u]-spfa.dis[v];
		}
	}
	_rep(i,1,n){
		LL ans=0;
		dj.solve(i,n);
		_rep(j,1,n) if(dj.dis[j]!=Inf)
		dj.dis[j]-=spfa.dis[i]-spfa.dis[j];
		_rep(j,1,n)
		ans+=1LL*j*dj.dis[j];
		enter(ans);
	}
	return 0;
}

连通分量

无向图的割顶与桥

定义

若删除节点 $u$ 将导致无向图的连通分量增加，则称 $u$ 为无向图的割顶。

若删除边 $e$ 将导致无向图的连通分量增加，则称 $e$ 为无向图的桥。

算法思想

考虑 $\text{dfs}$ 过程中建树。如果某条边指向的节点是第一次访问，则该边为树边，否则为反向边。易知，不同子树间不存在树边与反向边。

记 $\text{low}(u)$ 为 $u$ 及其后代不经过 $u$ 与 $fa_u$ 的树边能连回的最早祖先的 $\text{pre}$ 值。

顶点 $u$ 为割顶当且仅当 $u$ 为根节点且 $u$ 在树中有两个子节点或 $u$ 为非根节点且存在 $u$ 的一个子节点 $v$ 满足 $\text{low}(v)\ge \text{dfs_id}(u)$。

另外若此时还有 $\text{low}(v)\gt \text{dfs_id}(u)$，则 $(u,v)$ 为桥。

只需要 $\text{dfs}$ 过程维护一下 $\text{low}$ 数组即可，需要从树边的贡献和反向边的贡献两方面考虑，时间复杂度 $O(n+m)$。 

int low[MAXN],dfs_id[MAXN],dfs_t;
bool iscut[MAXN];
void dfs(int u,int fa){
	low[u]=dfs_id[u]=++dfs_t;
	int child=0;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa)continue;
		if(!dfs_id[v]){//树边贡献 
			dfs(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfs_id[u]&&u!=fa)
			iscut[u]=true;
			child++;
		}
		else
		low[u]=min(low[u],dfs_id[v]);//反向边贡献 
	}
	if(u==fa&&child>=2)//根节点特判 
	iscut[u]=true;
}

无向图的双连通分量

定义

给定一个连通图，以下条件等价：

  • 任意两点间至少存在两条点不重复的路径
  • 任意两条边都至少可以找到一个包含它们的简单环。
  • 图内部无割顶

若满足上述条件，则称该图是点-双连通的。对一个无向图，称点-双连通的极大子图为点-双连通分量。

类似的，给定一个连通图，以下条件等价：

  • 任意两点间至少存在两条边不重复的路径
  • 每条边都至少可以找到一个包含它的简单环。
  • 图内部无桥

若满足上述条件，则称该图是边-双连通的。对一个无向图，称点-双连通的极大子图为边-双连通分量。

算法思想

对点-双连通分量，有如下性质：

  • 每条边恰好属于一个点-双连通分量
  • 任意两个双连通分量间最多有一个公共点，且该点为割顶
  • 任意割顶至少属于两个不同的双连通分量

求点-双连通分量有两种方法，一种先一次 $\text{dfs}$ 求出割顶，再一次 $\text{dfs}$ 染色，染色过程中不经过割顶。

第二种方法为每求出一个割顶，立刻处理该连通分量，下面给出第二种方法的板子，时间复杂度 $O(n+m)$。

注意，该算法会导致孤立点不被计入任意一个连通分量。 

int low[MAXN],dfs_id[MAXN],dfs_t,bcc_id[MAXN],bcc_cnt;
vector<int> bcc[MAXN];
stack<pair<int,int> >Stack;
bool iscut[MAXN];
void dfs(int u,int fa){
	low[u]=dfs_id[u]=++dfs_t;
	int child=0;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa)continue;
		if(!dfs_id[v]){
			Stack.push(make_pair(u,v));
			dfs(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfs_id[u]){
				iscut[u]=true;
				pair<int,int> temp;
				bcc[++bcc_cnt].clear();
				while(true){
					temp=Stack.top();Stack.pop();
					if(bcc_id[temp.first]!=bcc_cnt){
						bcc_id[temp.first]=bcc_cnt;
						bcc[bcc_cnt].push_back(temp.first);
					}
					if(bcc_id[temp.second]!=bcc_cnt){
						bcc_id[temp.second]=bcc_cnt;
						bcc[bcc_cnt].push_back(temp.second);
					}
					if(temp.first==u&&temp.second==v)
					break;
				}
			}
			child++;
		}
		else if(dfs_id[v]<dfs_id[u]){
			Stack.push(make_pair(u,v));
			low[u]=min(low[u],dfs_id[v]);
		}
	}
	if(u==fa&&child<2)
	iscut[u]=false;
}
void find_bcc(int n){
	mem(dfs_id,0);
	mem(iscut,0);
	mem(bcc_id,0);
	dfs_t=bcc_cnt=0;
	_rep(i,1,n){
		if(!dfs_id[i])
		dfs(i,i);
	}
}

对边-双连通分量，有如下性质：

  • 除了桥不属于任意一个边-双连通分量，其他每条边恰好属于一个点-双连通分量
  • 任意两个双连通分量间无公共点和公共边

求边-双连通分量有两种方法，与求点-双连通分量类似。

例题

洛谷p3225

题意

给定 $n$ 个点，$m$ 条边。要求选择若干点作为逃生点，使得删去任意一个点后任意其他点均能达到某个逃生点。

输出最少需要选择的点数和选择最少的点数的方案数。

题解

考虑先求出所有点-双连通分量，记点-双连通分量的度为该点-双连通分量中的割点数。

易知若点-双连通分量的度等于 $0$，该点-双连通分量中必须设立两个逃生点，逃生点位置任意。

若点-双连通分量的度等于 $1$，该点-双连通分量中必须设立一个逃生点，逃生点不能是割点。

若点-双连通分量的度大于 $1$，则删去任意一个点后该点-双连通分量中仍然可以到达其他度为 $1$ 的点-双连通分量，不需要设置逃生点。

若某个点为孤立点，需要额外设立一个逃生点。

查看代码

查看代码 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cctype>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <cassert>
#define _for(i,a,b) for(int i=(a);i<(b);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
inline int read_int(){
	int t=0;bool sign=false;char c=getchar();
	while(!isdigit(c)){sign|=c=='-';c=getchar();}
	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
	return sign?-t:t;
}
inline LL read_LL(){
	LL t=0;bool sign=false;char c=getchar();
	while(!isdigit(c)){sign|=c=='-';c=getchar();}
	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
	return sign?-t:t;
}
inline char get_char(){
	char c=getchar();
	while(c==' '||c=='\n'||c=='\r')c=getchar();
	return c;
}
inline void write(LL x){
	register char c[21],len=0;
	if(!x)return putchar('0'),void();
	if(x<0)x=-x,putchar('-');
	while(x)c[++len]=x%10,x/=10;
	while(len)putchar(c[len--]+48);
}
inline void space(LL x){write(x),putchar(' ');}
inline void enter(LL x){write(x),putchar('\n');}
const int MAXN=505,MAXM=505;
struct Edge{
	int to,next;
}edge[MAXM<<1];
int head[MAXN],edge_cnt;
void Insert(int u,int v){
	edge[++edge_cnt].next=head[u];
	edge[edge_cnt].to=v;
	head[u]=edge_cnt;
}
int low[MAXN],dfs_id[MAXN],dfs_t,bcc_id[MAXN],bcc_cnt;
vector<int> bcc[MAXN];
stack<pair<int,int> >Stack;
bool iscut[MAXN];
void dfs(int u,int fa){
	low[u]=dfs_id[u]=++dfs_t;
	int child=0;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa)continue;
		if(!dfs_id[v]){
			Stack.push(make_pair(u,v));
			dfs(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfs_id[u]){
				iscut[u]=true;
				pair<int,int> temp;
				bcc[++bcc_cnt].clear();
				while(true){
					temp=Stack.top();Stack.pop();
					if(bcc_id[temp.first]!=bcc_cnt){
						bcc_id[temp.first]=bcc_cnt;
						bcc[bcc_cnt].push_back(temp.first);
					}
					if(bcc_id[temp.second]!=bcc_cnt){
						bcc_id[temp.second]=bcc_cnt;
						bcc[bcc_cnt].push_back(temp.second);
					}
					if(temp.first==u&&temp.second==v)
					break;
				}
			}
			child++;
		}
		else if(dfs_id[v]<dfs_id[u]){
			Stack.push(make_pair(u,v));
			low[u]=min(low[u],dfs_id[v]);
		}
	}
	if(u==fa&&child<2)
	iscut[u]=false;
}
void find_bcc(int n){
	mem(dfs_id,0);
	mem(iscut,0);
	mem(bcc_id,0);
	dfs_t=bcc_cnt=0;
	_rep(i,1,n){
		if(!dfs_id[i])
		dfs(i,i);
	}
}
int main()
{
	int kase=0,n,m,u,v;
	while(m=read_int()){
		n=0,edge_cnt=0;
		mem(head,0);
		while(m--){
			u=read_int(),v=read_int();
			n=max(n,u),n=max(n,v);
			Insert(u,v);
			Insert(v,u);
		}
		find_bcc(n);
		int ans1=0;
		unsigned long long ans2=1;
		_rep(i,1,bcc_cnt){
			int cnt=0;
			_for(j,0,bcc[i].size()){
				if(iscut[bcc[i][j]])
				cnt++;
			}
			if(cnt==1)
			ans1++,ans2*=bcc[i].size()-1;
			else if(cnt==0)
			ans1+=2,ans2*=bcc[i].size()*(bcc[i].size()-1)/2;
		}
		_rep(i,1,n){
			if(!bcc_id[i])
			ans1++;
		}
		printf("Case %d: %d %llu\n",++kase,ans1,ans2);
	}
	return 0;
}

有向图的强连通分量

算法思想

考虑 $\text{dfs}$ 求强连通分量，$\text{dfs}$ 遍历过程将每个点入栈。

只要保证在 $\text{dfs}$ 遍历完某个强连通分量后立即将所有该连通分量的点出栈并标记，即可区分每个强连通分量。

这等价于查询第一个进入栈且属于该强连通分量的点的编号。

一个点是第一个进入栈且属于该强连通分量的点等价于接下来入栈的点均无法访问该点的祖先节点，考虑用类似求点-双连通分量的方法维护。 

int dfs_id[MAXN],low[MAXN],dfs_t,scc_id[MAXN],scc_cnt;
vector<int> scc[MAXN];
stack<int>Stack;
void dfs(int u){
	low[u]=dfs_id[u]=++dfs_t;
	Stack.push(u);
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		if(!dfs_id[v]){
			dfs(v);
			low[u]=min(low[u],low[v]);//树边更新 
		}
		else if(!scc_id[v])//反向边更新 
		low[u]=min(low[u],dfs_id[v]);
	}
	if(low[u]==dfs_id[u]){
		int temp;
		scc[++scc_cnt].clear();
		while(true){
			temp=Stack.top();Stack.pop();
			scc_id[temp]=scc_cnt;
			scc[scc_cnt].push_back(temp);
			if(temp==u)
			break;
		}
	}
}
void find_scc(int n){
	mem(dfs_id,0);
	mem(scc_id,0);
	dfs_t=scc_cnt=0;
	_rep(i,1,n){
		if(!dfs_id[i])
		dfs(i);
	}
}
2020-2021/teams/legal_string/jxm2001/图论_1.1594719605.txt.gz · 最后更改: 2020/07/14 17:40 由 jxm2001

页面工具

除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki
京ICP备20018844号-3