526互联

强连通分量

发布时间 2023-09-11 20:03:24作者: star_road_xyz

强连通图判定

从一个点出发，可以遍历整张图，再将所有的边反向，从同一点出发，可以遍历整张图，则该图是强连通图

Tarjan求有向图强连通分量

\(\text{dfn[u]}\) 表示点 \(u\) 的dfs序，\(\text{low[u]}\) 表示点 \(u\) 可以走到的dfs序最小的点

我们在dfs树上，当一个点的 \(\text{low[u]}=\text{dfn[u]}\) ,即它无法进一步向上走时，我们就找到了一个强连通分量

Code:

int dfn[N],low[N],ins[N],stk[N],top,ts,tot,scc[N];
inline void tarjan(int u)
{
	dfn[u]=low[u]=++ts;
	ins[u]=1;
	stk[++top]=u;
	for(int i=head[u];i;i=edge[i].nxt)
	{
		int v=edge[i].v;
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(ins[v]) low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==low[v])
	{
		int x;++tot;
		do{
			x=stk[top--];
			scc[x]=tot;
			ins[x]=0;
		}while(x!=u);
	}
}

Trick：出栈顺序为拓扑序的倒序

Kosaraju算法

算法流程

先将图 \(G\) 所有的边反转得到图 \(G'\) ，计算 \(G'\) 的拓扑序并按照 \(G'\) 的拓扑序对 \(G\) 进行深度优先搜索

证明

对于两个点 \(x,y\) ，如果在图 \(G\) 中存在 \(x\rightarrow y\) ，拓扑序中 \(x\) 在 \(y\) 前面，即 \(G'\) 中存在 \(x\rightarrow y\) ，即 \(G\) 中存在 \(y\rightarrow x\) ，因此 \(x,y\) 在同一强连通分量中

HAOI2006 受欢迎的牛

题面

给定 \(n\) 个点 \(m\) 条边的有向图，求出能够被所有点到达的点

\(n\le 1\times 10^4,m\le 5\times 10^5\)

题解

求强连通分量，缩点。如果只有一个出度为 \(0\) 的点，那么这个点就是答案；如果这个数量大于等于 \(2\) ，那么无解

ZJOI2007 最大半连通子图

题面

有一个 \(n\) 个点 \(m\) 条边的有向图，你要找一个点集 \(S\)，使得 \(u,v\) 在 \(S\) 中有 \(u\) 能到达 \(v\) 或者 \(v\) 能到达 \(u\)
求出最大的 \(S\)，然后求有多少种选法

\(n\le 10^5,m\le 10^6\)

题解

缩点，要求的最大半联通子图一定是DAG上的一条链，分别记 \(f[i],g[i]\) 表示大小和方案数，dp即可

割点

定义

无向图中，删掉该点后使得图不连通，则该点为割点

求法

对于一个点 \(u\) 和它的一个儿子 \(v\)

  1. 如果该点是根，那么儿子数 \(\ge 2\) 就是割点
  2. 如果该点不是根，那么当 \(\text{low[v]}>=\text{dfn[u]}\) 时该点就是割点

Code:

int dfn[maxn],low[maxn],ts,rt;
std::vector<int> cut;
void tarjan(int u){
	dfn[u]=low[u]=++ts;
	int son=0;
	for(int i=head[u];~i;i=edge[i].next){
		int v=edge[i].v;
		if(!dfn[v]){
			++son;
			tarjan(v);
			low[u]=min(low[u],low[v]);
			if((u==rt&&son>1)||(u!=rt&&low[v]>=dfn[u]))
				cut.push_back(u);
		}
		else low[u]=min(low[u],dfn[v]);
	}
}

桥

定义

无向图中，删掉一条边使得图不连通，这条边就是桥

求法

对于一条边 \(u\rightarrow v\)，如果 \(\text{low[v]}>\text{dfn[u]}\) ，则该边就是桥

Code:

int dfn[maxn],low[maxn],ts,rt;
std::vector<pii> bridge;
void tarjan(int u){
	dfn[u]=low[u]=++ts;
	for(int i=head[u];~i;i=edge[i].next){
		int v=edge[i].v;
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
			if(low[v]>dfn[u])
				bridge.push_back(mkp(u,v));
		}
		else low[u]=min(low[u],dfn[v]);
	}
}

变双联通分量/无向图缩点

边双连通分量

删掉该点集中任意一条边都不会影响该点集的连通性，则称该点集为一个边双强连通分量

Code:

inline void tarjan(int u,int fa)  
{  
    low[u]=dfn[u]=++ts;  
    ins[u]=1;  
    stk[++top]=u;  
    for(int i=head[u];i;i=edge[i].nxt)  
    {  
        int v=edge[i].v;  
        if(v==fa) continue;  
        if(!dfn[v])         {  
            tarjan(v,u);  
            low[u]=min(low[u],low[v]);  
        }  
        else low[u]=min(low[u],dfn[v]);  
    }  
    if(low[u]==dfn[u])  
    {  
        int x;++tot;  
        do{  
            x=stk[top--];  
            ins[x]=0;  
            dcc[x]=tot;  
        }while(x!=u);  
    }  
}

DFS树求割点/桥

对于每一条非树边 \((u,v)\) ，让 \(u+1\) ，让 \(v-1\) （注意这里一定是返租边），那么就可以求出每一边/点的覆盖次数，覆盖次数为 \(0\) 的就是割点/桥

动态加边维护桥

上面那个做法可以在线完成

可以使用一个并查集维护当前双联通分量中的点，记录一下每个双联通分量中最高的点。

然后对于一条非树边，暴力将这些点合并起来即可

因为一条边最多被合并一次，需要不超过 \(\mathcal O(m)\) 次的并查集操作

点双联通分量/圆方树

点双连通分量

删掉点集中的任意一个点，该点集仍然连通，则称该点集是一个点双连通分量

圆方树

原图中所有的点作为圆点，对于每一个点双，我们建立一个方点，让这个方点连接点双中的每一个点，那么所有的度数大于 \(1\) 的圆点都是割点

实际题目中，可以给圆方树的圆点/方点赋上不同的权值，再通过dp、树剖等方式来计算答案

Code:

int dfn[N],low[N],ts,tot,stk[N],top,val[N],sum;
vector<int> G[N];
inline void tarjan(int u)
{
	++sum;
	dfn[u]=low[u]=++ts;
	stk[++top]=u;
	val[u]=-1;
	for(int i=head[u];i;i=edge[i].nxt)
	{
		int v=edge[i].v;
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u])
			{
				int x;++tot;
				do{
					x=stk[top--];
					++val[tot];
					G[x].emplace_back(tot);
					G[tot].emplace_back(x);
				}while(x!=v);
				++val[tot];
				G[u].emplace_back(tot);
				G[tot].emplace_back(u);
			}
		}
		else low[u]=min(low[u],dfn[v]);
	}
}

小Trick

给你一个图，每条边都只在一个环内，等价于每个点双联通分量是一条边或者一个环

POJ 3177 Redundant Paths

题面

给定 \(n\) 个点 \(m\) 条边的无向图，求至少需要加多少条边使得整张图成为边双联通分量

\(n\le 1\times 10^4,m\le 5\times 10^4\)

题解

缩点，以任意一个度数大于 \(1\) 的点为根，记叶子数为 \(l\) ，答案即为 \(\lceil \frac{l}2 \rceil\)

POI2008 BLO-Blockade

题面

给定 \(n\) 个点 \(m\) 条边的无向图，求将与每个点四周的边去掉之后有多少对点不连通 （\((x,y)\),\((y,x)\) 算两种情况）

\(n\le 1\times 10^5,m\le 5\times 10^5\)

题解

对于每一个点 \(i\)

  1. 如果 \(i\) 不是割点，那么就会产生以 \(2(n-1)\) 对与 \(i\) 有关的不连通点对
  2. 如果 \(i\) 是割点，设删掉与 \(i\) 有关的边之后产生了 \(k\) 个连通块，那么答案就为

    \[2(n-1)+\sum_{i=1}^k\sum_{j=1,j\neq i}^k\text{siz}[i]\times \text{siz} [j] \]

    考虑优化，我们有

    \[\sum_{j=1,j\neq i}^k\text{siz}[j]=n-\text{siz}[i]-1 \]

计算答案即可

HNOI2012 矿场搭建

题面

给定 \(n\) 个点 \(m\) 条边的无向图，要求从中选出最少的关键点，使得无论删除哪个点，其余的点都存在通往关键点的路径，求出关键点数量和方案数

\(n\le 500,m\le 1000\)

题解

建立圆方树，对于所有叶节点，它们不是割点，不会影响连通性，如果该点为割点那么设 \(f[u]\) 表示删掉点 \(u\) 时其子树内最少的关键点数量，\(g[u]\) 表示方案数，分圆方两种情况讨论

  1. 该点是圆点，那么有

    \[\begin{cases}f[u]=\sum_{v\in \text{son}_u}\max(f[v],1)\\g[u]=\sum_{v\in\text{son}_u}g[v]\end{cases} \]

    其中当 \(f[v]=0\) 时，\(g[v]=\text{siz}[v]\)
  2. 该点是方点，那么有

    \[\begin{cases}f[u]=\sum_{v\in \text{son}_u}f[v])\\g[u]=\sum_{v\in\text{son}_u}g[v]\end{cases} \]

P4630 [APIO2018] 铁人两项 （圆方树上dp）

题目

题解

考虑到当我们固定\(s,f\)时，我们\(c\)的选择就是\(s\)到\(f\)所有简单路径的并，然后减去\(2\)(因为\(c\)不可以选在\(s,f\)处)

进一步考虑，\(s\)到\(f\)简单路径的并就是路径上点双大小的并

所以建出原图的圆方树，将方点的权值设为这个点双中圆点的个数，将圆点的权值设为\(-1\)，那么从\(s\)到\(f\)简单路径的并就是圆方树上\(s\)到\(f\)的路径

我们设 \(f_i\) 表示 \(s,f\) 在 \(i\) 子树中的方案数，考虑枚举中转点 \(c\)，分两种情况转移

  • 点 \(c\) 是圆点时，假设它有 \(4\) 棵子树，它的子树对答案的贡献是

\[S_1S_2+S_1S_3+S_1S_4+S_2S_3+S_2S_4+S_3S_4 \]

看上去这个转移是 \(\mathcal O(n^2)\) 的,是我们可以这么做

\[S_1S_2+(S_1+S_2)S_3+(S_1+S_2+S_3)S_4 \]

所以我们每次记一个前缀子树和，然后乘上下一个子树的大小进行转移，这是\(\mathcal O(n)\)的

  • 当\(c\)是方点，如果\(s,f\)不在这个点双内，那么其贡献一定被这个点双中的圆点中就已经统计过了，所以考虑如何计算\(s,f\)在点双内的方案数
  1. 如果 \(s,f\) 中只有一个在点双中，那么 \(c\) 可以选的位置就有 \(deg-1\) 个，总共有 \(deg\times (deg-1)\) 次贡献，但是当 \(f\) 选在了割点处，那么\(c\)就无处可选了，乘的另外一部分是相同的，所以整个就少选了\(deg\) 次，所以总次数就变成了 \(deg\times (deg-2)\)
  2. 如果 \(s,f\) 都在点双内部，显然可以选择的位置就有 \(deg-2\) 个

所以在上面圆点的转移乘上 \(deg-2\) 的系数就行了