题解：P10480 可达性统计

Oct_ · 2024-05-18 17:37:49 · 题解

题目传送门

解题思路（超详细）

解法一：拓扑序加动态规划

按照什么顺序来更新呢？

注意到该图是有向无环图，那么其中的节点就满足拓扑序。

对于拓扑序列来说，前面的点一定会指向后面的点。所以我们可以从后往前处理，对于遍历到点 x，其指向的节点的可达点就已经固定了。于是当前点 x 的可达点就是指向节点的所有可达点。

最后要求是以每个点为起点的到达点个数，从后往前转移，要反向更新，反向建边。

如何记录状态？

不能直接将子节点的可达点个数相加，因为子节点间的可达点可能有重复。对于重复的元素只取一个，我们可以想到或操作。

注意：一个点可到达点的数量等于其指向的点的所有可达点取或。

可以将每个点的所有可达点进行状态压缩，用二进制中的 0 和 1 表示对于一个点可不可达。可达为 1，否则为 0。

为了方便操作，这里采用 STL 中的 bitset 来存储这个二进制。

从后往前遍历拓扑序列，对于当前位置 x，其可达点状态压缩对应二进制 f_x 就可以直接和其所指向节点所对应的二进制 f_{tx} 直接取或。

Code：

//c++20
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
map<int,int> mp;
const int N=30010;
int T,n,m,k;
int a[N],ru[N];
vector<int> e[N];
bitset<N> f[N];
void topsort()
{
    queue<int> que;
    for(int i=1;i<=n;i++) if(!ru[i]) que.push(i);
    while(que.size())
    {
        int x=que.front();
        que.pop();
        f[x][x] = 1;
        for(auto tx:e[x])
        {
            f[tx]|=f[x];
            ru[tx]--;
            if(ru[tx]==0) que.push(tx);
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    while(m--)
    {
        int x,y;cin>>x>>y;
        e[y].pb(x);
        ru[x]++;
    }
    topsort();
    for(int i=1;i<=n;i++) cout<<f[i].count()<<"\n";
    return 0;
}

解法二：记忆化搜索

因为是求每个点作为起点能够到达的点数，所以就从每个点出发，向外走，由起点往外更新。那么用记忆化搜索就要正常建边。

由此可见：

一般记忆化搜索是正常从前往后走，正常建边；

而拓扑序加动态规划却是将后面点的处理完毕之后，再用后面的状态更新前面状态。那么，拓扑序加动态规划的做法一般就要反向建边。

步骤：

从一点 x 出发：

如果走到一个点 tx 发现之前没有走过，那么从这个点递归，返回来的结果就是从这个点出发的答案。
否则，该位置已经存储了从该点 tx 出发的答案，直接用即可。不需要继续递归。
将当前点 x 更新，传回从当前点出发的答案。

Code：

//c++20
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
map<int,int> mp;
const int N=30010;
int T,n,m,k;
int a[N];
vector<int> e[N];
bitset<N> f[N];
bitset<N> dfs(int x)
{
    f[x][x] = 1;
    for(auto tx:e[x])
    {
        if(f[tx].count()) f[x] |= f[tx];
        else f[x]|=dfs(tx);
    }
    return f[x];
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    while(m--)
    {
        int x,y;cin>>x>>y;
        e[x].pb(y);
    }
    for(int i=1;i<=n;i++)
        if(!f[i].count()) dfs(i); //保证每个点都要走过
    for(int i=1;i<=n;i++) cout<<f[i].count()<<endl;
    return 0;
}

完结撒花！