164. 可达性统计(拓扑排序+数位dp)[通俗易懂]

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

给定一张 N 个点 M 条边的有向无环图，分别统计从每个点出发能够到达的点的数量。

输入格式
第一行两个整数 N,M，接下来 M 行每行两个整数 x,y，表示从 x 到 y 的一条有向边。

输出格式
输出共 N 行，表示每个点能够到达的点的数量。

数据范围
1≤N,M≤30000

输入样例：
10 10
3 8
2 3
2 5
5 9
5 9
2 3
3 9
4 8
2 10
4 9
输出样例：
1
6
3
3
2
1
1
1
1
1

#include<bits/stdc++.h>
using namespace std;
const int N = 3e4 + 10;
const int M = 3e4 + 10;
struct Edge{ 

int v,next;
}edge[M];
int head[N],cnt;
void add(int u,int v){ 

edge[cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt ++;
}
bitset<N>f[N];
int in[N],q[N],hh = 0,tt = 0;
int main(){ 

int n,m;
cin>>n>>m;
int x,y;
memset(head,-1,sizeof head);
for(int i = 0;i < m;i ++){ 

cin>>x>>y;
add(x,y),in[y] ++;
}
for(int i = 1;i <= n;i ++)if(!in[i])q[tt ++] = i;
while(hh < tt){ 

int t = q[hh ++];
for(int i = head[t];~i;i = edge[i].next){ 

int v = edge[i].v;
if((-- in[v]) == 0)q[tt ++] = v;
}
}
for(int i = tt - 1;i >= 0;i --){ 

int j = q[i];
f[j][j] = 1;
for(int k = head[j];~k;k = edge[k].next){ 

int v = edge[k].v;
f[j] |= f[v];
}
}
for(int i = 1;i <= n;i ++){ 

cout<<f[i].count()<<endl;
}
return 0;
}