2020年3月20日グラフ幅優先探索,グラフ,深さ優先探索,連結成分,Union-Find,連結成分のサイズ,同じ連結成分か判定

連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。

グラフ \(G=(V,E)\) 上の2頂点 \(u,v\) が同じ連結成分に属しているか判定するアルゴリズムについてです。 ...

2020年3月20日グラフ幅優先探索,グラフ,深さ優先探索,連結成分,連結成分の数

連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。

連結成分は3つアルゴリズム

グラフ \(G=(V,E)\) の連結成分の個数を数えるアルゴリズム:

「未探索」 ...

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

問題概要

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

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

2020年1月18日データ構造競プロ,データ構造,連結成分,Union-Find

2つの集合が共通する要素を持たない時に「互いに素」であると言い、このような集合の集まりを「素集合系」などと言います。

素集合系の例

素集合系は、いくつかの木構造を用いることで管理することができます。1つの集合は1つの木を用い ...