054 - Takahashi Number（★6）の解説

何の話かと言うと

atcoder.jp

この問題、公式解説では、「新たな頂点を追加してリンク数を削減する」というテクニックが紹介されています。実は、これを知らなくても、もう少し自然な発想で「本質的に同じ解法」にたどり着けるという話をします。

基本的な考え方

論文の共著者を（重さ1）のリンクで接続したグラフを作成して、「研究者1」からの最短距離をBFS（幅優先探索）で計算します。この際、共著者のリストからリンクの情報を愚直に構成すると、次のような処理になるでしょう。

  link = [[] for _ in range(N+1)]
  for _ in range(M):
    K = int(f.readline())
    R = list(map(int, f.readline().split()))
    for i in range(K):
      for j in range(i, K):
        link[i] = j
        link[j] = i

しかしながら、 であることから、この2重ループは で TLE になります。

2重ループを用いずにリンク情報を構成する方法としては、次のように、研究者ごとに共著者リストを（重複を気にせずに）積み上げる方法があります。

  link = [[] for _ in range(N+1)]
  for _ in range(M):
    K = int(f.readline())
    R = list(map(int, f.readline().split()))
    for i in range(K):
        link[i].append(R)

この場合、研究者 i からリンクされた研究者 j を取得する際は、次のような2重ループを使用します。

  for r in link[i]:
    for j in r:
      # j は i からリンクされたノード
      # 重複処理のチェックが必要

しかしながら、この方法の場合、重複が多すぎて、BFS の探索で TLE します。困りましたね。。。

論文単位で重複排除

上記の（2つ目の）アイデアにおいて、重複がどのように生じるかを考察してみましょう。ある論文 X に [i, j, k, l] の4人の研究者が入っていた場合、i, j, k, l のそれぞれに対して、[i, j, k, l] というリンク情報が追加されます。

そして、BFS による探索中に、はじめに、研究者 i の高橋数が決まったとします。すると、次のステップで、論文 X を通じて、j, k, l の高橋数が決まります。この時点で、論文 X の役割は終わります。つまり、j, k, l が持つ [i, j, k, l] というリンク情報は不要になります。

つまり、リンク情報は、論文単位で処理されていき、1つの論文は1回だけ処理すれば十分なのです。

そこで、研究者 i のリンク情報を

link[i] = [r1, r2, r3,...] # r1, r2, r3 は研究者 i が参加した論文のインデックス

という形で保存して、明示的に論文単位で処理を進めます。そして、論文ごとに「処理済みフラグ」を用意しておき、処理済みフラグが立った論文は、まるごとスキップします。実装を示すと次の通りです。

  N, M = map(int, f.readline().split())
  paper = [[] for _ in range(N+1)] # paper[i] 研究者 i が参加した論文
  authors = [[] for _ in range(M)] # authors[p] 論文 p の著者
  tkn = [10**30] * (N+1)
  tkn[1] = 0
  flag = [False] * M # 論文ごとの処理済みフラグ
 
  for p in range(M):
    K = int(f.readline())
    R = list(map(int, f.readline().split()))
    authors[p] = R
    for i in range(K):
      paper[R[i]].append(p)
 
  q = deque()
  q.append(1)
  while q:
    i = q.popleft()
    n = tkn[i]
    for p in paper[i]: # 論文単位でリンクを処理
      if flag[p]: # 処理済みの論文はスキップ
        continue
      flag[p] = True
      for j in authors[p]:
        if n + 1 < tkn[j]:
          tkn[j] = n + 1
          q.append(j)

これで、無事に通ります。

atcoder.jp

「新たな頂点」と「論文」の対応関係

と、ここまでを理解した上で、再度、公式解説 の図を見てください。

ここでは、論文ごとに「新たな頂点」を用意して、これを経由して、論文の共著者をリンクしています。この場合、論文 X の共著者の1人、i の高橋数が（他のリンク経由で）決定すると、論文 X に対応した頂点を通じて、他の共著者の高橋数が決まります。この時点で、論文 X に対応した頂点が処理済みになるので、これ以降は、論文 X を介したつながりはすべて「論文Xに対応した頂点」部分でブロックされることになります。

はい。

これは、先ほどの「論文単位でリンクを処理する」という実装と本質的に同じことですね。

公式解説をいきなりみると、「新たな頂点を追加する」という発想がどこから生まれたか不思議に感じるかもしれませんが、グラフのリンク構造が「論文」という固まりで構成されているからこそ、このようなテクニックが利用できるわけなのです。