图论提高

dolires / 2023-08-03 / 原文

复健\(Day7\)

图论一

\(DGA:\)有向无环图 \(SCC:\)强连通 \(BCC:\)双连通

强联通:有向图中,两个顶点至少存在一条路径(两个顶点可以互相到达)

强连通图:每两个顶点都强连通的有向图

强连通分量:有向图的极大强连通子图

\(1.\)有向图的强连通分量

问题模型:

对于一些存在依赖关系的模型,若其建图是一个\(DAG\),则可以直接通过拓扑排序解决,但是如果其中有环则需要特殊处理

对于有环的情况,会出现一些互相依赖的关系,这些关系组成了一个强连通分量,根据题目要求的性质,对于这个强连通分量可以将其缩成一个点

将所有强连通分量缩成点后即可在\(DAG\)上求解

有向图边的类型

使用\(DFS\)从任意节点遍历有向图时,可以得到\(DFS\)

每一条边和\(DFS\)树的关系,可以分成一下四种:

树枝边:\(DFS\)树上的边,即指向未访问过节点的边 前向边:指向\(DFS\)树中子树中节点的边

后向边:指向\(DFS\)树中父亲的边 横叉边:其他边,即指向\(DFS\)树中非子树的边

\(Tarjan\)

在一个有向有环图上\(DFS\),找出每一个强连通分量

考虑每个强连通分量里根最近的那个点,这些点将\(DFS\)树分割成了许多个子树,每个子树中的点组成了一个强连通分量

分割的方法是在\(DFS\)同时另外维护一个栈存放节点,离开分割点时把分割点往下的部分全部取出来就是一个强连通分量

维护一个数组\(low\)\(low[u]\)代表点\(u\)所能到达子树中的深度最小的点的\(dfs\)序编号(\(dfn[u]\)则表示\(u\)\(dfs\)序编号)

初始\(low[u]=dfn[u]\),对于边\((u,v)\),若为树枝边,则用\(low[v]\)更新;若为后向边,则用\(dfn[v]\)更新;若为前向边,因为指向的点的信息已经通过树枝边传递过来,所以无需更新;若为横叉边,则只想另一个强连通分量,无需更新

\(low[u]==dfn[u]\)时,就是一个分割点

模板\(P3387\)

https://www.luogu.com.cn/problem/P3387

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 10010
using namespace std;

int head[maxn],tot;

void Edge
{
	int v,nxt;
	Edge(){}
	Edge(int v,int nxt):v(v),nxt(nxt){}
}ed[maxn<<1];

inline void add(int u,int v)
{
	ed[tot]=Edge(v,head[u]);
	head[u]=tot++;
}

int s[maxn],s_top;
int dfn[maxn],low[maxn];
int scccnt,sccnum[maxn];
int dfscnt;

inline void tarjan(int now)//缩点
{
	dfn[now]=low[now]=++dfscnt;
	s[s_top++]=now;
	for(int i=head[now];~i;i=ed[i].nxt)
	{
		int v=ed[i].v;
		if(!dfn[v)//树枝边
		{
			tarjan(v);
			low[now]=min(low[now],low[v]);
		}
		else if(!sccnum[v])//后向边
		{
			low[now]=min(low[now],dfn[v]);
		}
	}
	if(dfn[now]==low[now])
	{
		scccnt++;
		do
		{
			sccnum[s[--s_top]]=scccnt;
		}while(s[s_top]!=now);
	}
}

int main()
{
	memset(head,-1,sizeof(head));
	int n,m;
	cin>>n>>m;
}

\(2.\)无向图的双连通分量

无向图的双连通性

对于一个无向图:点双连通:删去任何一个点仍然连通 边双连通:删去任何一条边仍然连通

即任意两点之间至少存在两条不经过同一中间点(边)的路径

点双连通必定边双连通,边双连通具有传递性(而点连通无)

若不满足双连通性,割点(割顶):删去后原图不连通的顶点的集合 割边(桥):删去后原图不连通的边集合

割边\((u,v)\)删去后变成两个连通块,\(v\)无法到达\(u\)前面的点

割点\(u\)删去后会有至少一个子树中的点无法到达\(u\)前面的点(根节点需特判,只要其多于一条树枝边,则是割点)

无向图的\(dfs\)树只有后向边和树枝边

模板(求割点)\(P3388\)

https://www.luogu.com.cn/problem/P3388

inline void tarjan(int now,int fa)//缩点
{
	dfn[now]=low[now]=++dfscnt;
	s[s_top++]=now;
	bool flag=false;
	for(int i=head[now];~i;i=ed[i].nxt)
	{
		int v=ed[i].v;
		if(v==fa&&!flag)
		{
			flag=true;
			continue;
		}
		if(!dfn[v])//树枝边
		{
			tarjan(v,now);
			low[now]=min(low[now],low[v]);
		}
		else if(!bnum[v])//后向边
		{
			low[now]=min(low[now],dfn[v]);
		}
	}
	if(dfn[now]==low[now])
	{
		bcccnt++;
		do
		{
			bnum[s[--s_top]]=bcccnt;
		}while(s[s_top]!=now);
	}
}
模板(求割边) \(P8436\)

https://www.luogu.com.cn/problem/P8436

\(3.\)树的直径

一张图中,\(dis(u,v)\)的最大值

可用树形\(DP\)计算,也可以两遍\(BFS\)来计算

树的重心:以某个点为根时,最大子树节点数最小,则这点被称作树的重心

其他充要条件:每个子树大小都不大于\(\frac{n}{2}\)//到所有点的距离和最小

当且仅当图的节点数\(n\)为偶数且有一条边链接两个大小均为\(\frac{n}{2}\)的子树时,树有两个重心,即使这条边的两个端点

int sz[maxn];
inline int dfs_sz(int now,int f)
{
	sz[now]=1;
	for(int i=head[now];~i;i=ed[i].nxt)
	{
		int v=ed[i].v;
		if(!vis[v]&&v!=f) sz[now]+=dfs_sz(v,now);
	}
	return sz[now];
}

inline int dfs_find(int now,int f,int tot)
{
	for(int i=head[now];~i;i=ed[i].nxt)
	{
		int v=ed[i].v;
		if(!vis[v]&&v!=f)
		{
			if((sz[v]<<1)>tot) return dfs_find(v,now,tot);
		}
	}
	return sz[now];
}

inline int dfs_findg(int s)
{
	dfs_sz(s,-1);
	return dfs_find(s,-1,sz[s]);
}
模板\(POJ1655\)

\(4.\)\(LCA\)

最近公共祖先:对于两个点\(u,v\),其祖先中深度最大的公共点被称为最近公共祖先,记作\(LCA(u,v)\)

树上前缀和与差分\(sum[u]\)记录\(u->root\)路径上的某种信息(满足可减性)的前缀和,则用\(LCA\)则可求出\(u->v\)路径上的前缀和

比如:信息在点上:\(sum[u]+sum[v]-2\times sum[lca(u,v)]+val[lca(u,v)]\) 信息在边上:\(sum[u]+sum[v]-2\times sum[lca(u,v)]\)

倍增求\(LCA\)

int fa[maxn][20],dep[maxn],d[maxn];
inline void build_lca(int now)
{
	for(int i=1;i<20&&fa[now][i];i++)
	{
		fa[now][i]=fa[fa[now][i-1]][i-1];
	}
	for(int i=head[now];~i;i=ed[i].nxt)
	{
		int v=ed[i].v;
		if(v==fa[now][0]) continue;
		fa[v][0]=now;
		dep[v]=dep[now]+1;
		d[v]=d[now]+ed[i].nxt;
		build_lca(v);
	}
}

inline int get_lca(itn x,int y)
{
	if(dep[x]!=dep[y])
	{
		if(dep[y]>dep[x]) swap(x,y);
		for(int i=19;i>=0;i--)
		{
			if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
		}
	}
	if(x==y) return;
	for(int i=19;i>=0;i--)
	{
		if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
	}
	return fa[x][0];
}

例如区间最大值(最小值)满足可加性,但是不满足可减性

例题

\(1.\)最优贸易

https://www.luogu.com.cn/problem/P1073

\(2.\)校园网

https://www.luogu.com.cn/problem/P2746

\(3.\)冗余路径

https://www.luogu.com.cn/problem/P2860

\(4.\)联合权值

https://www.luogu.com.cn/problem/P1351