标签：sz 图论 int 提高连通 dfs low now

复健\(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];
}

例如区间最大值（最小值）满足可加性，但是不满足可减性

例题

标签：sz,图论,int,提高,连通,dfs,low,now
From： https://www.cnblogs.com/iwillenter-top1/p/17603393.html

图论提高