データ構造の一つであるDisjoint Setsと、それを管理するUnion-Findアルゴリズムについて勉強した内容のまとめです。 この記事の内容 Disjoint Sets とは何か Disjoint Sets の実装のアイディア 例題を解く Disjoint Sets とは？ 複数の集合を考えたとき、そ…

連結グラフと連結成分について簡単にまとめてから、問題を解いていきます。 連結グラフ グラフに含まれる全ての頂点が他のいずれかの頂点とリンクしているようなグラフを連結グラフと言います。こんな感じ。 連結成分 あるグラフの部分グラフのうち、極大で…

グラフの基本的な内容です。グラフが隣接リストの形で与えられたとき、隣接行列に直します。 隣接リストと隣接行列 隣接リスト 配列Aを用意します。頂点uに対して、A[u]はuと隣接する全ての頂点を格納します。 隣接行列 ２次元配列Aを用意します。頂点iから…

優先度付きキューをヒープを使って実装します。標準ライブラリに入っていますが、勉強するために自分でやってみました。 最後に標準ライブラリの優先度付きキューの使い方も見てみます。 目標 実装を通して優先度付きキューを理解する。 標準ライブラリを使…

今回の主題は二分ヒープです。ヒープはデータ構造の一種。メモリのヒープ領域とは異なります。 完全二分木 上の図のような二分木を完全二分木と言います。全ての葉の深さが同じで、全ての内部ノードが２つの子を持たなければなりません。このように、葉の一…

二分探索木とは何かを簡単に説明してから、実装します。この記事では二分探索木に対する基本的な操作である要素の挿入・探索・削除ができるようになることを目標としています。 二分探索木とは？ 探索木というデータ構造があります。各ノードがキーと値を持…

データ構造第3弾、今回は連結リストを実装してみます。 これまでスタックやキューを実装してきましたが、今回はちょっとそれらより難しそうです。 目標 標準ライブラリに入っている連結リストを、自分で実装してみることで理解する。 双方向連結リスト 双方…

C++でデータ構造を実装してみるシリーズ。今回はキューを勉強しました。 標準ライブラリにありますが、勉強のために自分で実装します。 目標 キューを自分の手で実装してみる。 キュー キューは先入れ先出し（FIFO: First In First Out）を特徴とするデータ…

プロコンのための勉強の一環としてデータ構造を学習しています。今回はスタックです。 C++の標準ライブラリに入っていますが、勉強のために自分で実装してみます。 目標 スタックを実装する。 スタックとは 後入れ先出し（LIFO: Last In First Out）を特徴と…

木というデータ構造があります。プロコンやグラフ理論の勉強をしていると出てくると思います。木ってなに？という方や、だいたいどんなものかは知っているけど実装したことはないという方に向けて、まず基本的なところをざっくり説明して、それから問題を解…