[进阶指南] AcWing 164. 可达性统计

[ 传 送 门 ]

前言

不怕死的我 直接dfs 毫无意义问的直接AC(TLE) 了真不错 后面优化了一下还是 tle (我直接人间怀疑 ? ? ?)

有向无环图(DAG) 彻头彻尾不清楚这个给的是干嘛的 后面看题解才知道 是 拓扑排序专场 (呜呜呜，太久没做top了 都忘完了)

思路

• 求出 拓扑逆序
• 对拓扑序的能到达的边进行 求ans
• 又因为 前面的点能到的边 后面的点一定能到 所以 答案求并即可求得前面的

别问我 bitset 我也不清楚呜呜呜 我先挂在这 位运算一窍不通

CODE

#include 
using namespace std;
const int N = 3e4+10;
int n,m;
int d[N];
vector e[N];
vector top;
bitset f[N];
void topsort()
{
    top.clear();
    queue q;
    for(int i=1; iy;
        d[y]++;
        e[x].push_back(y);
    }
    find();
}
int main()
{
    ios::sync_with_stdio(false);
    solve();
    return 0;
}