思路
考虑从每一个 \(d_i \neq -1\) 的点开始往外走 \(d_i\) 步，然后所有这些点走到的点的集合取交集就是答案，复杂度是 \(\Theta(n^2)\) 的。
注意到我们需要对一些集合取交，容易想到 bitset 优化，此时的复杂度瓶颈在于 BFS 的次数。
因为 \(u \leadsto v\) 的最短路等于 \(v \leadsto u\) 的最短路，考虑将原先的起点看作终点，从原先的起点倒着走走到原来的终点，每一步距离为 \(-1\)。
可以直接上多源 Dijkstra，判断每一个 \(d_u \neq 1\) 是否和跑出来的 \(dis_u\) 相同即可。因为边权全部为 \(-1\) 可以把 Dijkstra 换成 BFS，实现上当队顶的 \(dis_u > d_x\) 时将 \(x\) 丢到队列里面即可。
最后复杂度是 \(\Theta(\frac{nm}{\omega})\)。
Code
#include <bits/stdc++.h>
#define re registerusing namespace std;const int N = 5e4 + 10,M = 2e5 + 10;
int n,m,tot,now;
int d[N],dis[N];
int idx,h[N],ne[M],e[M];
bitset<N> tmp,st[N];
vector<int> ans,S[N];inline int read(){int r = 0,w = 1;char c = getchar();while (c < '0' || c > '9'){if (c == '-') w = -1;c = getchar();}while (c >= '0' && c <= '9'){r = (r << 3) + (r << 1) + (c ^ 48);c = getchar();}return r * w;
}inline void add(int a,int b){ne[idx] = h[a];e[idx] = b;h[a] = idx++;
}inline void bfs(){queue<int> q;fill(dis,dis + n + 3,-1);while (!q.empty() || ~now){if (q.empty()){while (~now && S[now].empty()) now--;if (~now){for (int x:S[now]){q.push(x); dis[x] = d[x];} S[now--].clear();}}else if (dis[q.front()] == now){for (int x:S[now]){q.push(x); dis[x] = d[x];} S[now--].clear();}if (q.empty()) break;int u = q.front(); q.pop();if (~d[u] && d[u] != dis[u]){puts("0"); exit(0);}if (!dis[u]) continue;for (re int i = h[u];~i;i = ne[i]){int v = e[i];if (!~dis[v] || dis[v] == dis[u] - 1){if (!~dis[v]) q.push(v);st[v] |= st[u]; dis[v] = dis[u] - 1;}}}
}int main(){memset(h,-1,sizeof(h));n = now = read(),m = read();for (re int i = 1,a,b;i <= m;i++){a = read(),b = read();add(a,b); add(b,a);}for (re int i = 1;i <= n;i++){tot += ~(d[i] = read());st[i][i] = 1;if (~d[i]){tmp[i] = 1; S[d[i]].push_back(i);}} bfs();for (re int i = 1;i <= n;i++){if ((!dis[i] || !~dis[i]) && (st[i] & tmp) == tmp) ans.push_back(i);} printf("%d\n",ans.size());for (int x:ans) printf("%d ",x);return 0;
}