题解：P10480 可达性统计

· · 题解

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 记录