自动搬运

查看原文

来自洛谷，原作者为

	Atserckcn 愿你的刀仍然锋利

搬运于2025-08-24 22:58:23，当前版本为作者最后更新于2024-06-09 22:09:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P10480 可达性统计 题解

题目简述：

给定一个 $N$ 个点，$M$ 条边的有向无环图，统计从每个点出发所能经过的最多点数。

思路简述：

由于是有向无环图，我们不难想到用拓扑排序进行求解。当然你不用拓扑排序，暴力也是可以的，下文会提到。然而拓扑排序预处理完后，我们需要怎么统计呢？

这时候，我们就需要用到一个特殊的容器——bitset！！

bitset 简述：

bitset 可以看作是一个数组，但是它仅存真伪值（即 bool）。

因为 bitset 过于冷门，下面是它的用法介绍（更详细的在这里）：

定义一个 bitset 型数组 f[MAXN]：

bitset<MAXN> f[MAXN];//对，和vector或queue差不多

查看某个 bitset 变量的 true 的数量：

f[i].count();

至于其他的运算情况，跟普通的变量差不多，不予阐述。

好啦，上述成员函数已经够您做完这道题了，继续看思路吧。

具体实施方案：

将所有点的入度统计下来，依次从入度的小到大遍历每个点，计算入度，然后遍历每个点。因为能够遍历的点的数量一定是递增的，所以我们赋值可以用到或运算，即前面访问过的，将其延续下来，需要用到状态压缩的基础知识。

核心代码：

void dfs(int u)//以u为出发点
{
	if(book[u]) return;//已经访问过啦
	book[u]=true;
	for(int i=head[u];i;i=edge[i].pre)//链式前向星遍历
	{
		dfs(edge[i].to);
		f[u]|=f[edge[i].to];//看清楚，是|=
	}
	return;
}

具体代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int MAXN=30005;
bitset<MAXN> f[MAXN];
struct EDGE{//结构体存图
	int from,to,pre;
}edge[MAXN];
bool book[MAXN];
int u,v,cnt,head[MAXN],t;
queue<int> q;//用于拓扑排序
int in[MAXN];
void add(int from,int to)//加边
{
	edge[++cnt].from=from;
	edge[cnt].to=to;
	edge[cnt].pre=head[from];
	head[from]=cnt;
	return;
}
void dfs(int u)//核心代码，上述
{
	if(book[u]) return;
	book[u]=true;
	for(int i=head[u];i;i=edge[i].pre)
	{
		dfs(edge[i].to);
		f[u]|=f[edge[i].to];
	}
	return;
}
vector<int > num;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) f[i][i]=true;//初始化不能漏！
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		in[v]++;//入度+1
		add(u,v);
	}
	for(int i=1;i<=n;i++)//拓扑排序基础流程
		if(!in[i])
			q.push(i),num.push_back(i);
	while(!q.empty())
	{
		t=q.front();
		q.pop();
		for(int i=head[t];i;i=edge[i].pre)//遍历每条连边
		{
			if(--in[edge[i].to]<=0)//加入队列
			{
				q.push(edge[i].to);
				num.push_back(edge[i].to);
			}
		}
	}
	for(auto i:num)//遍历num
		dfs(i);
	for(int i=1;i<=n;i++)
		printf("%d\n",f[i].count());
	return 0;
}

当然，你不用拓扑排序，直接朴素算法，也是没问题的，如下：

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int MAXN=30005;
bitset<MAXN> f[MAXN];
struct EDGE{
	int from,to,pre;
}edge[MAXN];
bool book[MAXN];
int u,v,cnt,head[MAXN];
void add(int from,int to)
{
	edge[++cnt].from=from;
	edge[cnt].to=to;
	edge[cnt].pre=head[from];
	head[from]=cnt;
	return;
}
void dfs(int u)
{
	if(book[u]) return;
	book[u]=true;
	for(int i=head[u];i;i=edge[i].pre)
	{
		dfs(edge[i].to);
		f[u]|=f[edge[i].to];
	}
	return;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) f[i][i]=true;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	for(int i=1;i<=n;i++)
	{
		dfs(i);
		printf("%d\n",f[i].count());
	}
	return 0;
}

对，我太懒了，就是改了改，没重写。

拓扑排序方法 AC 记录

朴素算法 AC 记录