Niue'z Blog

BFS Numbering

Posted at — Oct 5, 2019

僕が木上クエリコンで出題した問題で使った手法です.

No.899 γatheree - yukicoder

アルゴリズム

BFSを行って頂点に番号を順番に振っていきます.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

になります. ここで, BFSは深さが浅い順に頂点を見ることに注目すると,

0 [1 2] 3 4 5 6 7 8 9 10 11 12 13 14
0 1 2 [3 4 5 6] 7 8 9 10 11 12 13 14

また同様に

0 1 2 [3 4] 5 6 7 8 9 10 11 12 13 14
0 1 2 3 4 5 6 [7 8 9 10] 11 12 13 14

つまりBFS Numberingは, 深さを同じくする頂点を列の区間に落とし込むことができます.

実装はこんな感じ(この例では, 距離2までの頂点を記録しています)

i64 N;
cin >> N;
idx.resize(N + 1, -1);//idx[v] := Euler Tourの列での頂点vの位置
L1.resize(N + 1, -1);//距離1にある頂点の列の左端
R1.resize(N + 1, -1);//右端
L2.resize(N + 1, -1);//距離2にある頂点の列の左端
R2.resize(N + 1, -1);//右端
p.resize(N + 1, -1);//親
G.resize(N + 1);
for(int i = 0;i < N - 1; i++) {
  i64 a, b;
  cin >> a >> b;
  G[a].push_back(b);
  G[b].push_back(a);
}
G[N].push_back(0);

queue<i64> que;
que.push(N);
idx[N] = vec.size();
vec.push_back(N);
while(!que.empty()) {
  i64 v = que.front();
  que.pop();
  for(auto x: G[v]) {
    if(idx[x] != -1) continue;
    que.push(x);
    idx[x] = vec.size();
    vec.push_back(x);
    p[x] = v;

    if(L1[v] == -1) L1[v] = idx[x];
    R1[v] = idx[x] + 1;

    i64 pp = p[v];
    if(pp != -1) {
      if(L2[pp] == -1) L2[pp] = idx[x];
      R2[pp] = idx[x] + 1;
    }
  }
}

わりと素直に書ける

感想

新出で驚いた 典型にしていこうな