从结尾往回搜就是反向边,然后API也有统计位上是true的方法
import java.util.*;
public class Main{
static int N = 60010, n, m;
static int e[] = new int[N], ne[] = new int[N], h[] = new int[N], idx;
static int d[] = new int[N], q[] = new int[N], hs[] = new int[N];
static BitSet f[] = new BitSet[N];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
Arrays.fill(h, -1);
Arrays.fill(hs, -1);
while(m -- != 0){
int a = sc.nextInt();
int b = sc.nextInt();
add(h, a, b);
add(hs, b, a);
d[b] ++;
}
topsort();
for(int i = 0; i < N; i ++){
f[i] = new BitSet(N);
f[i].set(i, true);
}
for(int i = n-1; i >= 0; i --){
int j = q[i];
for(int k = hs[j]; k != -1; k = ne[k]){
int t = e[k];
f[t].or(f[j]);
}
}
for(int i = 1 ; i <= n; i ++){
System.out.println(f[i].cardinality());
}
}
static void topsort(){
int hh = 0, tt = -1;
for(int i = 1; i <= n; i ++){
if(d[i] == 0) q[++ tt] = i;
}
while(hh <= tt){
int t = q[hh ++];
for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
if(-- d[j] == 0) q[ ++ tt] = j;
}
}
}
static void add(int h[], int a, int b){
e[idx] = b; ne[idx] = h[a]; h[a] = idx ++;
}
}