[AtCoder] ABC157 D – Friend Suggestions 解説(400点)

2020年3月3日AtCoderグラフ, 競プロ, 連結成分, Union-Find

問題概要

N 人がいて、M 組が友達関係、K 組がブロック関係である。それぞれに対して以下を満たす「友達候補」が何人いるか答えよ。

  • まだ友達関係ではない
  • ブロック関係ではない
  • 友達関係を辿ってたどり着ける

制約

  • \(2 ≤ N ≤ 10^5\)
  • \(0 ≤ M ≤ 10^5\)
  • \(0 ≤ K ≤ 10^5\)
  • 友達関係とブロック関係は重複しない

考え方

友達候補というのは、友達関係を辿って到達できる人物です。この性質はグラフの構造に非常によく似ています。

人間を頂点・友達関係を辺としたグラフとして考えると、「友達候補」は以下の条件を満たす必要があります。

  • 間に辺がない
  • パスがある(同じ連結成分内である)
  • ブロック関係ではない

よって、「友達候補」の数は以下のように計算可能です。

友達候補の数 = 連結成分のサイズ-1 – 自身からの辺(友達関係)の数 – 連結成分内のブロック関係の数

1を引くのは、自身を「友達候補」から外すためです。

自身からの辺(友達関係)の数 は問題に与えられています。

連結成分ごとのサイズや、連結成分内のブロック関係の数は、深さ優先探索や Union-Find Tree などを用いて取得可能です。

解法(DFS)

  1. DFS を用いて、「自身がどの連結成分に含まれるか」「連結成分ごとのサイズ」をあらかじめ求める
  2. 「友達候補の数 = 連結成分のサイズ-1 – 自身からの辺(友達関係)の数 – 連結成分内のブロック関係の数」を各人間に対して計算する

C++での実装例

解法(Union-Find Tree)

  1. Union-Find Tree を用いて、1つの連結成分を一つの集合(木) としてまとめる
  2. 「友達候補の数 = 連結成分のサイズ-1 – 自身からの辺(友達関係)の数 – 連結成分内のブロック関係の数」を各人間に対して計算する

C++での実装例

Tree のサイズを求めたいので、Union-Find Tree の併合時の工夫として、サイズを利用したものを使うと良いです。