連結成分

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

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

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

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

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

「未探索」 ...

問題概要

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

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

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

素集合系の例

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