P10480 可达性统计

题目要求一幅图的所有顶点所能到达的顶点数，最直观的想法是通过DFS或BFS暴力搜索，但是在最坏情况下，要访问 $N$ 个顶点和 $M$ 条边，又有 $N$ 个顶点，总的时间复杂度就是

O(N(N+M))

而 $N$ 和 $M$ 能去到 $30000$ ,别说时间上不允许，空间就先告急了。

好在题目中的图是有向无环图（DAG），有良好的性质，那就是可以找到入度为0的顶点进行拓扑排序，这样我们就可以从后往前推，每次将访问的顶点与其相邻的顶点的可达集合两两合并即可，这部分用位图完成。

拓扑排序为Kahn算法，时间复杂度：

O(N+M)

遍历过程需要访问所有的点，同时访问其相邻的边：

O(M*N/w),其中w为机器位长

#include <iostream>
#include <vector>
#include <queue>
#include <bitset>

std::vector<int> topological_sort(std::vector<int>& in_degree,std::vector<std::vector<int>>& adj)
{
    std::queue<int> q;
    std::vector<int> res;
    for (int i = 1; i < in_degree.size(); i++)
    {
        if (!in_degree[i])
            q.push(i);
    }
    while (!q.empty())
    {
        int k = q.front();
        q.pop();
        for (int i = 0; i < adj[k].size(); i++)
        {
            in_degree[adj[k][i]]--;
            if (!in_degree[adj[k][i]])
                q.push(adj[k][i]);
        }
        res.push_back(k);
    }
    return res;
}

const int N = 30000 + 1;
std::bitset<N> bs[N];

int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>> adj(n+1);
    std::vector<int> in_degree(n + 1);
    for (int i = 0; i < m; i++)
    {
        int x, y;
        std::cin >> x >> y;
        adj[x].push_back(y);
        in_degree[y]++;
    }
    std::vector<int> topo_order = topological_sort(in_degree, adj);
    for (int i = n-1; i >= 0; i--)
    {
        int k = topo_order[i];
        bs[k].set(k);
        for (int j = 0; j < adj[k].size(); j++)
        {
            bs[k] |= bs[adj[k][j]];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        std::cout << bs[i].count()<<std::endl;
    }
    return 0;
}