@[Soda1445](/user/769917) 你考虑复杂了，这题其实很简单的。
```
很显然这是一道广搜题。为什么不是“SPFA”或“迪杰斯特拉”呢？因为题目中明确指出，“给出一个N个顶点M条边的无向无权图”，那么，每条边权就相当于1。很显然符合广搜的特点。
1.自环。很显然我们可以证明，删除自环对这道题没有影响。
2.重边。重边对这道题是有影响的，照样存储。
3.求最短路有几条。当访问到这个节点时，如果是第一次访问，将这个节点的答案+=他父节点的答案，并将这个节点推到队尾（push）；如果是第二次访问且当前的距离等于之前记录的距离，说明这是第二条最短路，同样，将这个节点的答案+=他父节点的答案，但不需要（push）了。
```
上面这段话是我从题解里面抄过来的，开始的时候没看明白。
比如说，点i，从点1到点i的最短距离是什么？？（灵魂拷问）
。。。。。
其实这个距离就是从点1到点i的bfs的搜索深度。
这题就是考察的bfs的搜索树，父节点x,子节点y， distance[y] = distance[x]+1.
下面是我的代码，马蜂比较丑而且没加注释，但是代码量比较少，我觉得你应该能看的懂。
```
#include <bits/stdc++.h>
#define f(i,a,b) for(int i=a;i<=b;i++)
#define g(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
using namespace std;
const int maxn = 1000005;
const int mod = 100003;
int n,m;
vector<int> g[maxn];
int ans[maxn];
int dep[maxn];
bool vis[maxn];
queue<int> q;
int main(){
scanf("%d %d",&n,&m);
for(int i = 1,u,v;i <= m;i++) {
scanf("%d %d",&u,&v);
if(u == v) continue;
g[u].push_back(v);
g[v].push_back(u);
}
ans[1] = 1,vis[1] = 1;
q.push(1);
while(!q.empty()) {
int x = q.front();
q.pop();
for(int i = 0,len = g[x].size();i < len;i++) {
int y = g[x][i];
if(vis[y] == 0) vis[y] = 1,dep[y] = dep[x] + 1,ans[y] += ans[x],q.push(y);
else {
if(dep[y] == dep[x] + 1) ans[y] += ans[x],ans[y] %= mod;
}
}
}
for(int i = 1;i <= n;i++) printf("%d\n",ans[i]);
return 0;
}
```
by mooktian @ 2024-03-12 09:38:15