TL;DR: 問題文では「判定」「同時更新」の2つの概念がありますが、これを深く考える必要はありません。

実は、以下の BFS でこの問題に正解できます。

• 人 \(i\) について、 \(i\) の友人で噂を知っている人数を \(L_i\) とする。
• 最初から噂を知っている友人を queue に入れる。これらの人物は便宜上 \(L_i=T\) としておく。
• queue から出てきた人物 \(x\) に対し、 queue が空になるまで以下を繰り返す。
  • \(x\) の全ての友人 \(i\) について、 \(L_i\) に \(1\) 加算する。
  • 加算の結果 \(L_i = T\) となれば、 \(i\) を噂を知る人物であると断定して queue に入れる。

証明:
この問題中では、噂を新たに知る人物がいなくなるまで操作を繰り返します。なので、以下の理屈が成り立ちます。

• ある人 \(x\) の周りに噂を知っている人物が \(T\) 人以上居たとする。
• すると、人 \(x\) は何日か後に いずれ噂を知ることになる 。

この理屈を拡張すると、

• ある人 \(y\) の周りに噂を知っている人物・あるいは いずれ噂を知ることになる人物 が \(T\) 人以上居たとする。
• すると、「いずれ噂を知ることになる人物が(十分な人数)噂を知る」というタイミングが必ず訪れることになり、そのタイミングで人 \(y\) は噂を知ることになる、つまり人 \(y\) も何日か後にいずれ噂を知ることになります。

これを連鎖的に繰り返していくと、この連鎖が停止したタイミングで周りに噂を知っている人物・あるいはいずれ噂を知ることになる人物が \(T\) 人以上居るような人物がいなくなります。このことで、それらの人物が全員噂を知ってもこれ以上噂を知ることができる人物がいなくなり、噂を知っている人物がこれ以上増えないことが確認できます。

時間計算量は \(O(N+M)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n,m,k,t;
  cin >> n >> m >> k >> t;
  int res=0;
  vector<int> level(n+1,0);
  queue<int> q;
  for(int i=0;i<k;i++){
    int c;
    cin >> c;
    level[c]=t;
    q.push(c);
    res++;
  }
  vector<vector<int>> g(n+1);
  for(int i=0;i<m;i++){
    int u,v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  while(!q.empty()){
    int od=q.front(); q.pop();
    for(auto &nx : g[od]){
      level[nx]++;
      if(level[nx]==t){
        q.push(nx);
        res++;
      }
    }
  }
  cout << res << "\n";
  return 0;
}