DFSを勉強してみた （ABC087から）
この記事で、言及していたDFSについて。相当基本的なものらしいので、勉強してみる。
例えば上で触れたABC087の解説動画。
重み付き有向グラフというのが何じゃそれ？と思っていたが、文字通り、点と点の間を重みの付いた向きのある線で結ぶグラフらしかった（何の説明にもなっていない感）。
この解説動画はとてもありがたい。文章よりも、解いている人の「ノリ」みたいなものが伝わってくる感じがする。
とはいえ、動画ではここから先はDFSなどで･･･ということになってしまったので勉強する。
回答例から
例のABC087のD問題の回答例から探ってみる。
Submission #2066827 - AtCoder Beginner Contest 087
まず、最初にいっぱいincludeなんたらが出てくる。これが良く分からない。
includeについて
によると、
- #include を使えば、別のファイルを埋め込むことができる。
- ファイル名を < > で囲めば設定されたフォルダの、" " で囲めば今のフォルダのファイルになる。
- ファイルの先頭でインクルードするファイルをヘッダーファイルと言う。
ということらしい。例えば、
#include<iostream>
なら、iostreamというフォルダ全体を埋め込んでいるということか。なんとなく分かった。こうして色々ライブラリなんかも読み込めるわけですか。
iostreamライブラリ
第 3 章 iostream ライブラリ (C++ ライブラリ・リファレンス)
によると、iostreamは標準入出力をつかさどるライブラリらしい。cinとか、coutとか。それは最初からおまじないでとりあえずつけておくべきものなわけだ。
vectorライブラリ（名前空間についても）
std::vector とは C++ で標準に使用できる便利な動的配列クラスのことらしい。
上のiostreamライブラリのときもそうだけど、「名前空間」というやつをなんか設定しておかないといけないらしい。そういえば、いつも
using namespace std;
という呪文を書いている。これがその名前空間の指定をする文らしい。iostreamも、vectorも、stdという名前空間を指定しておけばよいらしい。
記述の仕方
実際には記述の仕方が二種類あって、（上のページからの引用）
#include <vector> // ヘッダファイルインクルード int main() { std::vector<int> v; // ローカル変数として、v を生成 ..... }
#include <vector> // ヘッダファイルインクルード using namespace std; // 名前空間指定 int main() { vector<int> v; // ローカル変数として、v を生成 ..... }
こんな感じ。（１）変数を定義するたびに名前空間を指定する（２）最初にまとめて名前空間を指定する といった感じか。
そんなこんなでvectorライブラリを使う。
宣言の仕方
宣言の仕方は複数ある。
まず、動的に配列を宣言する方法（配列の要素数を指定しない）
std::vector<int> data; // int 型の動的配列 data の宣言
このようにしておくと、最初は要素数は０になる。push_back()などを使って要素を追加できるらしい。
次に、
std::vector<int> data(123); // int 型で、初期要素数 123 の動的配列 data の宣言
このようにすると、要素を初めから指定できる。
あと、二次元以上の配列を宣言するには、
のように入れ子にして使う。
algorithmライブラリ
（難しいけどちゃんと書いてありそう）
Algorithms library - cppreference.com
３つ挙げたうち、３つめのリンクのページより
The algorithms library defines functions for a variety of purposes (e.g. searching, sorting, counting, manipulating) that operate on ranges of elements. Note that a range is defined as
[first, last)wherelastrefers to the element pastthe last element to inspect or modify.
たぶん一定の配列の要素からいろいろ抜き出したりなんだりができるのかな？
恐らく多機能すぎて今ここでは勉強しきれないと思われるので、とりあえず置いておいて、後ほど具体例で勉強しましょう。
utilityライブラリ
Utility library - cppreference.com
C++にはビット操作から部分適用までの機能を提供するユーティリティライブラリが多数含まれています。これらのライブラリは、大きく二つのグループに分けることができます。
ぱっと見、pair とか swap とかつかえそう？これもまあ、後でゆっくり見ましょう。
プログラムの前段階までになってしまったけれど、
とりあえずここまで。後ほど追記します。
