题目思路

本题难度较大，考虑使用bitset优化，如果求每个点的可达的点的数量需要$O(n^2)$，这必然超时。

使用bitset可以优化至$O(n^2/64)$，但是原来题目的数据范围过不去，在原来的数据缩小十倍的情况下可以过去。

所以本题的数据是原来的数据缩小十倍

bitset可以理解为固定长度的比特串，可以比较快速的做一些位操作。可以用每一位的0/1表示它是否可达，结合拓扑排序就可以求得所有节点的可达节点以及可以到达该节点的所有节点数量。

代码

C++

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second
#define endl '\n'
const int fastio = []() {
    cin.tie(0)->sync_with_stdio(false);
    return 0;
}();

const int N = 3e4;

void solve() {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> g(n), vg(n);
        vector<int> vec;
        vector<bitset<N>> in(n), out(n);
        for (int i = 0;i < n;++ i) {
        	in[i][i] = out[i][i] = 1;
        }
        while (m --) {
                int u, v;
                cin >> u >> v;
                -- u, -- v;
                if (u != v) {
                	g[u].emplace_back(v);
                	vg[v].emplace_back(u);
                }
        }
        auto topsort = [&](vector<vector<int>>&g) {
                vector<int> d(n, 0);
                queue<int> q;
                for (int i = 0;i < n;++ i) for (int j: g[i]) ++ d[j];
                for (int i = 0;i < n;++ i) {
                        if (!d[i]) q.push(i);
                }
                while(q.size()) {
                        int u = q.front();
                        q.pop();
                        for (int v: g[u]) {
                                if (-- d[v] == 0) q.push(v);
                                in[v] |= in[u];
                        }
                }
        };
        topsort(g);
        vector<int> cnt(n, 0);
        for (int i = 0;i < n;++ i) {
        	cnt[i] += in[i].count();
        	in[i].reset();
        	in[i][i] = 1;
        }
        topsort(vg);
        int ans = 0;
        for (int i = 0;i < n;++ i) {
        	if(in[i].count() + cnt[i] == n + 1) {
                ++ ans;
           }
        }
        cout << ans << endl;
}

signed main() {
        int T = 1;
        while(T --) {
                solve();
        }
}

会员可通过查看《已通过》的提交记录来查看其他语言哦~

题目描述

快递站共有$n$个快递点，$n$个快递点之间通过$m$条个快递站单向车道连接，快递员从任何一个快递站点出发，都无法通过单向车道回到该站点。也就是说，$n$个快递点组成一张有向无环图。对于快递点$u$，如果对于所有的快递点$v(v≠u)$，快递员都可以从$u$走到$v$，或者从$v$走到$u$，那么则评定站点$u$为超级快递点。请你帮忙计算，一共有多少个超级快递点。

注：本题为原题的easy版本，数据范围较小。

输入描述

第一行 2个数字$n(2≤n≤3*10^4)$，

$m(1≤m<3*10^5)$;n为快递点个数，m为单向车道个数

接下来的$m$行每行两个数字$u,v(1≤u,v≤n,u≠v)$，表示有一条站点$u$指向$v$的单向车道。

输出描述

请输出1个数字，表示超级快递点的个数。

样例

输入

7 7
1 2
2 3
3 4
4 7
2 5
5 4
6 4

输出

2

说明

快递点4可以到达 4，7，可以从1，2，3，5，6到达，评为超级快递点
快递点7可以到达7，可以从1，2，3，4，5，6到达，评为超级快递点