CH 2101 - 可达性统计 - [BFS拓扑排序+bitset状压]

题目链接：传送门

描述

给定一张N个点M条边的有向无环图，分别统计从每个点出发能够到达的点的数量。N,M≤30000。

输入格式

第一行两个整数N,M，接下来M行每行两个整数x,y，表示从x到y的一条有向边。

输出格式

共N行，表示每个点能够到达的点的数量。

样例输入

样例输出

题解：

首先，如果用 $f(x)$ 代表从点 $x$ 出发所能到达的所有点的集合，应有如下公式：

$f(x) = {x} \cup (\bigcup_{edge(x,y)}f(y))$

也就是说我们可以通过某种递推方式，递推出所有点的 $f(x)$。

由此想到有向无环图的拓扑序（对于图中任意一条有向边 $(x,y)$，在该序列中 $x$ 都出现在 $y$ 之前），对有向无环图的拓扑序逆向遍历计算，正好可以正确求出每个点的 $f(x)$。

另外，我们还可以用状压的方式来存储 $f(x)$，也比较方便转移和存储，这里我们用bitset容器来做状压。

关于bitset：

bitset<> num; 相当于定义了一个1000位的二进制数，其 $1$ 位占用 $1$ 个bit，也就是说 $8$ 位占用一个Byte。

由于估计时间复杂度是我们一般以 $32$ 位整数的运算次数为基准，因此 $n$ 位的bitset执行一次位运算的时间复杂度可以视作 $n/32$。

bitset支持的位运算有按位取反“~”、按位与“&”、按位或“|”、按位异或“^”、左移“<<”、右移“>>”（均用 $0$ 填充），还可以比较是否相等“==”和“!=”。

bitset支持 num[k] 这种形式进行取值或者赋值。根据上面的定义，范围为 num[] 到 num[] 。

bitset还支持：set()全部置 $1$、reset()全部置 $0$、count()统计 $1$ 的数目、any()查询是否存在 $1$、none()查询是否没有 $1$。

AC代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn=+;

int n,m;

int indg[maxn];

vector<int> e[maxn];

bitset<maxn> f[maxn];

vector<int> topo;

void TopoSort()

{

    topo.clear();

    queue<int> Q;

    for(int i=;i<=n;i++) if(indg[i]==) Q.push(i);

    while(Q.size())

    {

        int u=Q.front(); Q.pop();

        topo.push_back(u);

        for(auto v:e[u]) if(--indg[v]==) Q.push(v);

    }

}

int main()

{

    ios::sync_with_stdio();

    cin.tie(), cout.tie();

    cin>>n>>m;

    memset(indg,,sizeof(indg));

    for(int i=,x,y;i<=m;i++) cin>>x>>y, indg[y]++, e[x].push_back(y);

    TopoSort();

    for(int i=topo.size()-;i>=;i--)

    {

        int x=topo[i];

        f[x].reset(), f[x][x]=;

        for(auto y:e[x]) f[x]|=f[y];

    }

    for(int i=;i<=n;i++) cout<<f[i].count()<<endl;

}

巴特西

CH 2101 - 可达性统计 - [BFS拓扑排序+bitset状压]

描述

输入格式

输出格式

样例输入

样例输出

最新文章

热门文章