摘要
Title: 164. 可达性统计
Tag: 拓扑排序、bitset
Memory Limit: 64 MB
Time Limit: 1000 ms

164. 可达性统计

题意

给定一张 N 个点 M 条边的有向无环图，分别统计从每个点出发能够到达的点的数量。
思路
- 对图进行拓扑排序，在拓扑序列中从后往前进行遍历，利用bitset进行状态转移(前面的点只会用到后面的点的数量)
  （即拓扑排序的逆序）
- n给定的数值未知，可以使用bitset存储该点能到达其他所有点的集合，该位是1表示能到达，0表示不能到达,每个点的bitset中有多少个1表示能到达多少个点

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(0);                                                                                                        \
    cout.tie(0);
#define DEBUG(X) cout << #X << ": " << X << endl;
typedef pair<int, int> PII;

const int INF = 1E18;
const int N = 3e4 + 10;

bitset<N> b[N];

signed main()
{
    IOS;
    int n, m;
    cin >> n >> m;
    vector<int> deg(n + 1);
    vector<int> g[n + 1];

    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        deg[v] += 1;
    }

    // 找拓扑排序的头
    queue<int> q;
    for (int i = 1; i <= n; ++i)
    {
        if (!deg[i])
            q.push(i);
    }
    // 拓扑排序，并记下拓扑排序
    vector<int> tops;
    while (SZ(q))
    {
        int u = q.front();
        q.pop();
        tops.push_back(u);
        for (auto v : g[u])
        {
            deg[v]--;
            if (deg[v] == 0)
            {
                q.push(v);
            }
        }
    }

    // 逆序遍历拓扑排序
    for (int i = n - 1; i >= 0; --i)
    {
        int u = tops[i];
        b[u].set(u); // 自己能到自己
        for (auto v : g[u])
        {
            b[u] |= b[v];
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        cout << b[i].count() << '\n';
    }

    return 0;
}

164. 可达性统计

题意

思路

代码