重みが最小となる閉路を求めるアルゴリズム
最小コストの閉路：
任意の辺 e = (u,v) について以下を繰り返すグラフ G から e を取り除くv から u への最短経路 d を求める(ダイクストラ/BFS など)
d+cost(u, ...
ワーシャル・フロイド法での全点対最短経路を求めるアルゴリズム
任意の2頂点間の最短距離を求める問題を全点対最短経路問題といいます。
ワーシャル・フロイド法は、動的計画法を用いて全点対最短経路を求める有名なアルゴリズムです。
負の辺が含まれていても動作する負の閉路がある場 ...
プリム法による最小全域木を求めるアルゴリズム
無向グラフ \(G=(V,E)\) について、\(G\) の部分グラフ \(T\) が以下を満たす時、\(T\) は全域木（Spanning Tree) と言います。
\(T\) は木\(T\) では\(V\) の任意の ...
クラスカル法による最小全域木を求めるアルゴリズム
無向グラフ \(G=(V,E)\) について、\(G\) の部分グラフ \(T\) が以下を満たす時、\(T\) は全域木（Spanning Tree) と言います。
\(T\) は木\(T\) では\(V\) の任意の ...
グラフの2頂点が同じ連結成分に属するか判定するアルゴリズム
連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。
グラフ \(G=(V,E)\) 上の2頂点 \(u,v\) が同じ連結成分に属しているか判定するアルゴリズムについてです。 ...
グラフの連結成分の個数を求めるアルゴリズム
連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。
連結成分は3つアルゴリズムグラフ \(G=(V,E)\) の連結成分の個数を数えるアルゴリズム：
「未探索」 ...木の直径を求めるアルゴリズム
木に存在する2つノード間の最大距離を木の直径と言います。
重み無しの木でも、重み付きの木でも、木の最遠頂点間の距離が直径になります。
重み無しの木の例：
以下は直径が5となる木の例で
ダイクストラ法による単一始点最短経路を求めるアルゴリズム
グラフにおける単一始点最短経路問題とは、始点を固定した時に、他のすべての頂点への最短経路を求める問題のことです。
ダイクストラ法は、単一始点最短経路問題を解く時に利用され、利点としては
計算量が \(O(|E| \l ...ベルマンフォード法による単一始点最短経路を求めるアルゴリズム
グラフにおける単一始点最短経路問題とは、始点を固定した時に、他のすべての頂点への最短経路を求める問題のことです。
ベルマンフォード法は、単一始点最短経路問題を解く時に利用され、
負の辺が含まれているような場合でも適用 ...[AtCoder] ABC157 D – Friend Suggestions 解説（400点）
N 人がいて、M 組が友達関係、K 組がブロック関係である。それぞれに対して以下を満たす「友達候補」が何人いるか答えよ。
まだ友達関係ではないブロック関係ではない
友達関係を辿ってたどり着ける
制約\ ...