用的BFS

#include<bits/stdc++.h>
using namespace std;
const int MAXn=1e6+10,MAXm=2*1e6+10;
bool re[MAXn];
int ans[MAXn],d[MAXn];
vector <int> link[MAXm];
struct node{
	int fir,seco;
};
inline node make(int first,int second){
	node ans;ans.fir=first;ans.seco=second;return ans;
}
void BFS(){
	queue <node> Q;
	Q.push(make(1,0));
	memset(d,0x3f,sizeof(d));d[1]=0;
	re[1]=1;ans[1]=1;
	while(Q.size()){
		node S=Q.front();
		int u=S.fir,dis=S.seco;
		Q.pop();
		for(int i=0; i<int(link[u].size()); i++){
			if(!re[link[u][i]]){
				Q.push(make(link[u][i],dis+1));
				re[link[u][i]]=1;
				d[link[u][i]]=dis+1;
				ans[link[u][i]]+=ans[u];
				ans[link[u][i]]%=100003;
			}
			else{
				if(dis+1==d[link[u][i]]){
					ans[link[u][i]]+=ans[u];
					ans[link[u][i]]!=100003;
				}
			}
		}
	}
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	int k=1;
	for(int i=1;i<=m;i++){
		int x,y; scanf("%d%d",&x,&y);
		if(x==y) continue;
		else {
			link[x].push_back(y);
			link[y].push_back(x);
		}
	}
	BFS();
	for(int i=1;i<=n; i++){
		printf("%d\n",ans[i]%100003);
	}
	return 0;
}

（万分感谢看完 悬关）