当前位置：首页 > news >正文

洛谷题目：P10480 可达性统计题解（本题简）

news 2025/5/2 10:12:21

个人介绍：

题目传送门：

P10480 可达性统计 - 洛谷 (luogu.com.cn)

前言：

这道题要求在给定的有向无环图（DAG）中，统计从每个点出发能够到达的点的数量。下面是小亦为大家分享的解题思路：

#整体题目思路概括：

我们的核心目标是对图中的每个节点，找出它能到达的素有节点。由于图是有向无环图，我们可以利用深搜算法的特性，通过递归的方式从每个节点开始搜索其所有可达节点。为了高效地记录和合并可达节点的信息我们使用 bitset 数据结构。

##具体步骤：

1、图的表示：

我们使用临街表来表示有向无环图。邻接表是一种常见图的存储方式，对于图中的每个节点，我们用一个动态数组来存储从该节点出发的所有有向边的重点。

2、可达性记录：

使用 bitset 数组 reachable[MAXN] 来记录从每个节点能够到达的节点情况。

3、深搜：

3.1、递归搜索：定义一个 dfs 函数，用于从某个节点开始进行深搜。对于每个节点 u ，首先检查 reachable[u] 是否已经计算过，如果已经计算过的话则直接返回，碧莲重复计算。

3.2、自身可达性：将 reachable[u][u] 置为 1 ，表示节点 u 可以到达自身。

3.3、邻接节点搜索：遍历节点 u 的所有邻接节点 v ，递归调用 dfs(v) 来计算从节点 v 出发能够到达的节点。然后将 reachable[v] 合并到 reachable[u] 中，即 reachable[u] | = reachable[v] ,这一步使用按位或操作，将 reachable[v] 中为 1 的位也设置到 reachable[u] 中。

4、主函数处理：

4.1、输入读取：读取图的节点数量 n 和边的的数量 m ，并依次读取每条边的节点 x 和终点 y ，将 y 添加到 graph[x] 中，完成图的构建。

4.2、遍历节点：对图中的每个节点 i ，调用 dfs(i) 函数计算从该节点出发能够到达的节点。然后输出 reachable[i].count() , 即 reachable[i] 中为 1 的位的数量，也就是从节点 i 能够到达的节点数量。

###复杂度：

1、时间复杂度：

$O(N*(N+M)/32)$ 。

2、空间复杂度：

$O(N^2/8)$ 。

####代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 40000;
// 存储图的邻接表
vector<int> graph[MAXN];
// 用于记录从每个点出发能到达的点的情况
bitset<MAXN> reachable[MAXN];// 深度优先搜索函数
void dfs(int u) {if (!reachable[u].none()) return;reachable[u][u] = 1;for (int v : graph[u]) {dfs(v);reachable[u] |= reachable[v];}
}int main() {int n, m;cin >> n >> m;// 读入边信息，构建图for (int i = 0; i < m; ++i) {int x, y;cin >> x >> y;graph[x].push_back(y);}// 对每个点进行深度优先搜索for (int i = 1; i <= n; ++i) {dfs(i);// 输出从点 i 出发能到达的点的数量cout << reachable[i].count() << endl;}return 0;
}

感谢观看！！！