快递站共有n个快递点,n个快递点之间通过m条个快递站单向车道连接,快递员从任何一个快递站点出发,都无法通过单向车道回到该站点。也就是说,n个快递点组成一张有向无环图。对于快递点u,如果对于所有的快递点v(v=u),快递员都可以从u走到v,或者从v走到u,那么则评定站点u为超级快递点。请你帮忙计算,一共有多少个超级快递点。
注:本题为原题的easy版本,数据范围较小。
本题难度较大,考虑使用bitset优化,如果求每个点的可达的点的数量需要O(n2),这必然超时。
使用bitset可以优化至O(n2/64),但是原来题目的数据范围过不去,在原来的数据缩小十倍的情况下可以过去。
所以本题的数据是原来的数据缩小十倍
bitset可以理解为固定长度的比特串,可以比较快速的做一些位操作。可以用每一位的0/1表示它是否可达,结合拓扑排序就可以求得所有节点的可达节点以及可以到达该节点的所有节点数量。