补充知识点

最短路算法与图中顶点的拓扑序之间的关系：

• bfs算法
  当图中所有边权都相等时，bfs算法可用来求解最短路问题。当某个顶点出队（或入队）时，从起点到该顶点的最短路长度已经确定，这是因为bfs算法是从起点开始，逐层往下扩展的，首次到达该顶点时的路径长度就是最短路。因此，图中所有顶点的出对顺序就构成拓扑序。
• dijkstra算法
  某个顶点出队时，从起点到该顶点的最短路长度已经确定，这是dijkstra算法本身所表示的含义。因此图中所有顶点的出队顺序即构成拓扑序。
• bellman-ford(或spfa)算法
  当某个顶点入队时，只是表明到该顶点的路径长度变小了，有可能更新该顶点连接的其他顶点，但无法保证该长度一定是最短路径的长度。出队时的含义与入队的含义一致。因此，bellman-ford（或spfa）算法的入队（或出队）顺序不一定构成拓扑序。
  如果要使用此算法来解决此类问题，可进行这样的改进：先求出所有点的最短路径长度，再构建出图中节点的拓扑序，接着就是常规操作，使用DP求解路径数量。

本题思路与代码

对于本题而言，可使用bfs算法来求解最短路问题，同时维护最短路径数量。
注意起点的最短路径数量应初始化成1。

import java.util.*;

public class Main
{
    static int N = 100010, M = 400010, MOD = 100003, INF = 0x3f3f3f3f;
    static int n, m;
    static int[] h = new int[N];
    static int[] ne = new int[M];
    static int[] e = new int[M];
    static int idx;
    static int[] d = new int[N];
    static int[] cnt = new int[N];
    static LinkedList<Integer> q = new LinkedList<>();

    public static void add(int a, int b)
    {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }

    public static void bfs()
    {
        Arrays.fill(d, INF);
        d[1] = 0;
        cnt[1] = 1;
        q.addLast(1);

        while(!q.isEmpty())
        {
            int t = q.removeFirst();
            for(int i = h[t]; i != -1; i = ne[i])
            {
                int j = e[i];
                if(d[t] + 1 < d[j])
                {
                    d[j] = d[t] + 1;
                    cnt[j] = cnt[t];
                    q.addLast(j);
                }
                else if(d[t] + 1 == d[j])
                {
                    cnt[j] = (cnt[j] + cnt[t]) % MOD;
                }
            }
        }

    }

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        Arrays.fill(h, -1);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i = 0; i < m; i ++)
        {
            int a = sc.nextInt(), b = sc.nextInt();
            add(a, b);
            add(b, a);
        }

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