グラフの2頂点が同じ連結成分に属するか判定するアルゴリズム
連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。
グラフ \(G=(V,E)\) 上の2頂点 \(u,v\) が同じ連結成分に属しているか判定するアルゴリズムについてです。 ...
[AtCoder] ABC157 D – Friend Suggestions 解説(400点)
問題概要
ブロック関係ではない
友達関係を辿ってたどり着ける
制約\ ...
N 人がいて、M 組が友達関係、K 組がブロック関係である。それぞれに対して以下を満たす「友達候補」が何人いるか答えよ。
まだ友達関係ではないブロック関係ではない
友達関係を辿ってたどり着ける
制約\ ...
Union-Find Tree を理解する!素集合系を扱うデータ構造
2つの集合が共通する要素を持たない時に「互いに素」であると言い、このような集合の集まりを「素集合系」などと言います。
素集合系の例素集合系は、いくつかの木構造を用いることで管理することができます。1つの集合は1つの木を用い ...