@TOC
前言
不怕死的我 直接dfs 毫无意义问的直接AC(TLE) 了真不错
\
后面优化了一下还是 tle (我直接人间怀疑 ? ? ?)
有向无环图(DAG) 彻头彻尾不清楚这个给的是干嘛的
\
后面看题解才知道 是 拓扑排序专场 (呜呜呜,太久没做top了 都忘完了)
思路
- 求出 拓扑逆序
- 对拓扑序的能到达的边进行 求ans
- 又因为 前面的点能到的边 后面的点一定能到 所以 答案求并即可求得前面的
别问我 bitset 我也不清楚呜呜呜 我先挂在这 位运算一窍不通
CODE
#include <bits/stdc++.h>
using namespace std;
const int N = 3e4+10;
int n,m;
int d[N];
vector<int> e[N];
vector<int> top;
bitset<N> f[N];
void topsort()
{
top.clear();
queue<int> q;
for(int i=1; i<=n; i++)
if(d[i] == 0)
q.push(i);
while(!q.empty())
{
int u = q.front();
q.pop();
top.push_back(u);///存拓扑序
for(int i =0 ; i<e[u].size(); i++)
if(--d[e[u][i]] == 0)
q.push(e[u][i]);
}
}
void find()
{
topsort();
for(int i =top.size()-1; i>=0; i--)
{
int x = top[i];
f[x].reset(),f[x][x]=1;
for(int k = 0;k<e[x].size();k++)
f[x]|=f[e[x][k]];
}
for(int i=1;i<=n;i++)
cout<<f[i].count()<<endl;
}
void solve()
{
cin>>n>>m;
memset(d,0,sizeof d);
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
d[y]++;
e[x].push_back(y);
}
find();
}
int main()
{
ios::sync_with_stdio(false);
solve();
return 0;
}