算法分析

由于该图是拓扑图，计算每个点能到达的点可以通过集合的角度进行分析

状态表示

• f[i]:表示i点能到达的点的集合的数量

状态计算

假设j1,j2,...jk是i点可直接到达的点

• f[i] = f[i] U f[j1] U f[j2] U ... U f[jk]

步骤

• 1、对图进行拓扑排序，在拓扑序列中从后往前进行遍历，进行状态转移(前面的点只会用到后面的点的数量)

• 2、n给定的数值未知，可以使用BitSet存储该点能到达其他所有点的集合，该位是1表示能到达，0表示不能到达,每个点的BitSet中有多少个1表示能到达多少个点

时间复杂度 $(n * m)/32$

参考文献

算法提高课

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.BitSet;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int N = 30010,M = N;
    static int n;
    static int m;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int idx = 0;
    static int[] d = new int[N];
    static int[] qv = new int[N];
    static int qidx = 0;
    static BitSet[] all = new BitSet[N];
    static void add(int a,int b)
    {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    static void topsort()
    {
        Queue<Integer> q = new LinkedList<Integer>();
        for(int i = 1;i <= n;i ++)
        {
            if(d[i] == 0)
            {
                q.add(i);
                qv[qidx ++] = i; 
            }
        }

        while(!q.isEmpty())
        {
            int t = q.poll();

            for(int i = h[t];i != -1;i = ne[i])
            {
                int j = e[i];
                if(-- d[j] == 0)
                {
                    q.add(j);
                    qv[qidx ++] = j;
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        Arrays.fill(h, -1);
        while(m -- > 0)
        {
            String[] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            add(a,b);
            d[b] ++;
        }
        topsort();
        //每个点的数量初始值为1
        for(int i = 1;i <= n;i ++)
        {
            all[i] = new BitSet();
            all[i].set(i);
        }

        for(int i = qidx - 1;i >= 0;i --)
        {
            int j = qv[i];
            for(int k = h[j];k != -1;k = ne[k])
            {
                int x = e[k];
                all[j].or(all[x]);
            }
        }

        for(int i = 1;i <= n;i ++) System.out.println(all[i].cardinality());
    }
}