洛谷——P3906Geodetic集合

#include
#define N 101001
using namespace std;
int n,m,head[N],tot;
bool pvis[N];
struct nod {
int to,next;
} e[N];
void add(int u,int v) {
e[++tot].to=v,e[tot].next=head[u],head[u]=tot;
}
int q,d[N];
bool vis[N];
queue<int>Q;
vector<int>G[50];
void spfa(int x) {
while(!Q.empty()) Q.pop();
Q.push(x);
for(int i=1; i<=n; i++) G[i].clear();
memset(vis,0,sizeof(vis));
memset(d,0x3f,sizeof(d));
vis[x]=1,d[x]=0;
while(!Q.empty()) {
int u=Q.front();
Q.pop();
vis[u]=0;
for(int i=head[u]; i; i=e[i].next) {
int v=e[i].to;
if(d[v]>d[u]+1) {
d[v]=d[u]+1;
if(!vis[v]) {
G[v].clear();
G[v].push_back(u);
Q.push(v);
vis[v]=1;
}
} else if(d[v]==d[u]+1) {
G[v].push_back(u);
}
}
}
}
int an[N],tpt;
void dg(int u,int a) {
int sz=G[u].size();
an[++tpt]=u;
for(int i=0; i) {
int v=G[u][i];
if(v==a) continue;
dg(v,a);
}
}
int main() {
scanf("%d%d",&n,&m);
for(int a,b,i=1; i<=m; i++) {
scanf("%d%d",&a,&b);
add(a,b),add(b,a);
}
scanf("%d",&q);
for(int a,b,i=1; i<=q; i++) {
scanf("%d%d",&a,&b);
// memset(pvis,0,sizeof(pvis));
spfa(a);
memset(an,0,sizeof(an));
tpt=0;
dg(b,a);
an[++tpt]=a;
sort(an+1,an+1+tpt);
for(int j=1; j<=tpt; j++){
if(an[j]!=an[j+1]) printf("%d ",an[j]);
}
puts("");
}
return 0;
}