自动搬运

查看原文

来自洛谷，原作者为

	panyf **

搬运于2025-08-24 21:42:59，当前版本为作者最后更新于2021-05-30 12:55:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

传递闭包的四种求法

有向图传递闭包需要对每个点对 $(i,j)$，求出 $i$ 到 $j$ 是否连通。

做法 1：

直接 Floyd，$b_{i,j}=1$ 表示 $i$ 能到达 $j$，$b_{i,j}=0$ 表示不能到达。

枚举中转点 $i$，再枚举 $j,k$，转移方程：b[j][k]|=b[j][i]&b[i][k]。

可以用 bitset 优化：if(b[j][i])b[j]|=b[i]。

时间复杂度 $O(\dfrac{n^3}{w})$。

做法 2：

以每个点为起点深/广搜遍历整张图，求出能到达的所有点。

时间复杂度 $O(nm)$。

做法 3：

上一个做法不能用 bitset 优化，是因为可能存在环，不能记忆化。

考虑对强连通分量缩点（此题中保证是 DAG 就不用了）。

然后继续用做法 2，以每个点为起点 dfs。

若当前访问到边 $(i,j)$，$j$ 未被 dfs 过，则 dfs $j$。

然后 b[i]|=b[j]。

时间复杂度 $O(\dfrac{nm}{w})$。

适合稀疏图，在此题中效率最高。

做法 4：

依然是先缩点。

然后求出 DAG 的拓扑序。

按拓扑序每 $B$ 个点分一块，倒序求解。

对于每一块，在求出其中所有点的可达集合后，求出 $2^B$ 个子集的可达集合（一个子集的可达集合是其中所有点可达集合的并集），用 bitset 优化，这部分复杂度 $O(2^B\dfrac{n}{B}\dfrac{n}{w})$。

求一个点 $i$ 的可达集合，只需要枚举之后的每个块，通过子集的可达集合，一次更新以块中所有存在边 $(i,j)$ 的点 $j$ 为中转点的答案，这部分复杂度 $O(n\dfrac{n}{B}\dfrac{n}{w})$。

取 $B=\log n$，总复杂度 $O(\dfrac{n^3}{w\log n})$。

适合稠密图。

代码中取 $B=8$。

最后提一下此题做法。

显然是传递闭包模板题。

最坏情况下，所有不能确定大小关系的都要问一遍。

所以答案即为总的满足 $i\neq j$ 的无序对数 $\dfrac{n\times(n-1)}{2}$，减去已经确定大小关系的对数。

已经确定大小关系的对数，就是满足 $i$ 能到达 $j$ 且 $i\neq j$ 的数对 $(i,j)$ 个数。

做法 1

#include<bits/stdc++.h>
using namespace std;
const int N=1009;
bitset<N>b[N];
int main(){
	int n,m,i,j;
	for(scanf("%d%d",&n,&m);m--;)scanf("%d%d",&i,&j),b[i][j]=1;
	for(i=1;i<=n;++i)for(j=1;j<=n;++j)if(b[j][i])b[j]|=b[i];
	for(j=n*(n-1)/2,i=1;i<=n;++i)j-=b[i].count();
	printf("%d",j);
	return 0;
}

做法 2

#include<bits/stdc++.h>
using namespace std;
const int N=1009;
bool b[N];
int s;
basic_string<int>g[N];
void dfs(int x){for(int i:g[x])if(!b[i])b[i]=1,--s,dfs(i);}
int main(){
	int n,m,i,j;
	for(scanf("%d%d",&n,&m);m--;)scanf("%d%d",&i,&j),g[i]+=j;
	for(i=1,s=n*(n-1)/2;i<=n;++i)memset(b,0,N),dfs(i);
	printf("%d",s);
	return 0;
}

做法 3

#include<bits/stdc++.h>
using namespace std;
const int N=1009;
bitset<N>b[N];
basic_string<int>g[N];
void dfs(int x){
	b[x][x]=1;
	for(int i:g[x]){
		if(!b[i][i])dfs(i);
		b[x]|=b[i];
	}
}
int main(){
	int n,m,i,j;
	for(scanf("%d%d",&n,&m);m--;)scanf("%d%d",&i,&j),g[i]+=j;
	for(i=1,j=n*(n+1)/2;i<=n;++i)dfs(i),j-=b[i].count();
	printf("%d",j);
	return 0;
}

做法 4

#include<bits/stdc++.h>
using namespace std;
const int N=1009;
basic_string<int>g[N];
int p[N],d[N],q[N];//p[i]表示i在拓扑序的逆序中的排名
bool e[N][N];
bitset<N>b[N],o[259];
int main(){
	int n,m,i,j,l=0,r=0;
	for(scanf("%d%d",&n,&m);m--;)scanf("%d%d",&i,&j),g[i]+=j,++d[j];
	for(i=1;i<=n;++i)if(!d[i])q[++r]=i;//拓扑排序入队
	while(l<r){//拓扑排序
		i=q[++l],p[i]=n-l+1;
		for(int o:g[i])if(!(--d[o]))q[++r]=o;
	}
	for(i=1;i<=n;++i)for(int o:g[i])e[p[i]][p[o]]=1;//重新建边，i>j时e[i][j]才可能等于1
	for(i=1;i<=n;++i)if(b[i][i]=1,!(i&7)){
		for(j=1;j<256;++j)l=j&-j,o[j]=o[j^l]|b[i-7+__lg(l)];//求出一块的子集的bitset
		for(j=i+1;j<=n;b[j++]|=o[l])for(r=l=0;r<8;++r)if(e[j][i-7+r])l|=1<<r;//用子集的bitset更新之后的所有点
	}else for(j=min(n,i/8*8+8);j>i;--j)if(e[j][i])b[j]|=b[i];//更新当前块之后的点
	for(i=1,j=n*(n+1)/2;i<=n;++i)j-=b[i].count();
	printf("%d",j);
	return 0;
}