题意分析
因为是无向无权图，因此可以通过 BFS 求最短路。
BFS 找到即最优，因此找的时候递推即可。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
const int N=1e6,M=2e6,mod=100003;
struct edge{
int v,r;
}a[2*M+1];
int n,m,u,v,h[N+1],ans[N+1];
void create(int u,int v){
static int top=0;
a[++top]={v,h[u]};
h[u]=top;
}
void bfs(int s){
static int pl,dis[N+1];
queue<int>q;
q.push(s);
dis[s]=1;
ans[s]=1;
while(q.size()){
pl=q.front();
q.pop();
for(int i=h[pl];i>0;i=a[i].r){
if(dis[a[i].v]==0){
q.push(a[i].v);
dis[a[i].v]=dis[pl]+1;
ans[a[i].v]=ans[pl];
}else if(dis[pl]+1==dis[a[i].v])ans[a[i].v]+=ans[pl];
ans[a[i].v]%=mod;
}
}
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d %d",&u,&v);
create(u,v);create(v,u);
}bfs(1);
for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
