解法0 (TLE解法)

まず, 素直に考えると, 以下のようにして解くことができると考えられる.

グラフ \(G=(V(G) , E(G))\) を以下のようにして構成する: 頂点集合 \(V(G)\) は \(1\) 以上 \(N\) 以下からなる整数全体の集合, 辺集合 \(E(G)\) は以下のようにして定義される集合である.

\[ij \in E(G) \iff 研究者 i と研究者 j が一緒に執筆した共著が存在する\]

このとき, 研究者 \(i\) の高橋数が存在すれば, その値はグラフ \(G\) における頂点 \(1\) と頂点 \(i\) との距離と一致する. そして, これは幅優先探索 (BFS) で求めることが可能である.

しかし, このグラフ \(G\) の構成においては, \(N\) 人の研究者が合同で共著を執筆した場合, \(G\) は \(N\) 頂点の完全グラフとなるため, 辺の本数は \(\Theta(N^2)\) なる. よって, グラフの構成自体で計算量が \(\Theta(N^2)\) となり, 　実行時間制限に間に合わない.

解法1 (必要になったら辺を足す)

解法 0 における幅優先探索において, 実際に距離の計算に関係があるのは高々 \(N-1\) 本である (BFS木). 実際に距離の計算に寄与する可能性がある辺のみを見れば良い.

では, どのような辺が寄与する可能性があるのだろうか? 結論から言うと, 寄与する可能性があるのは, 各共著における, 一番最初に深さ優先探索のキューに加えられた頂点 \(i\) と (その共著を執筆した) のそれ以外の全ての頂点達である. よって, 各研究者がどの共著に関わったかを記録することにより, 頂点 \(i\) を取り出した際, 1回でも調べた共著に関する関係はクローズすることによって, 計算量を \(K_{\rm sum}:=\sum_{i=1}^M K_i\) とすることにより, \(O(N+M+K_{\rm sum})\) で求めることができる.

解法2 (超頂点を追加する)

また, 解法 1を発展させることで, 以下のような解法もある.

グラフ \(H=(V(H), E(H))\) を, 研究者と共著論文を頂点に持つ \((N+M)\) 頂点からなるグラフとする. ただし, 以下では \(k\) 番目の共著を \([k]\) と書くことにする. このとき, \(H\) の辺を

\[i [k] \in E(H) \iff 研究者 i は共著 [k] に関わっている\]

とする. なお, このグラフ \(H\) は二部グラフである. このとき, 2頂点 \(u,v \in V(H)\) 間の距離を \(\operatorname{dist}(u,v)\) と書くことにすると, 研究者 \(i\) の高橋数は (存在すれば) \(\frac{1}{2} \operatorname{dist}(1,i)\) である.