GCP の Credential の読み込み
Google Cloud Platform では認証情報をJSON形式などでダウンロードすることで外部のアプリケーションから BigQuery などのサービスにアクセスすることができます。しかし、認証情報を読み込ませるのに苦労したので解決までのメモを残しておきます。
環境
- Ubuntu 20.04
- Go 1.13
どこで詰まったのか
ドキュメントにあるようにJSONまでのパスを環境変数にセットしました。
export GOOGLE_APPLICATION_CREDENTIALS=/home/.../credential.json
さあ、これでアクセスできると考えプログラムを走らせたところ
Response: {
"error": "invalid_grant",
"error_description": "Token has been expired or revoked."
}。。。いや、今発行したばかりなのに期限切れとか取り消されたとかなんだよ。試しに、.bashrcにこの環境変数をセットして試してみましたがダメでした。echo $GOOGLE_APPLICATION_CREDENTIALSで確認するとちゃんとセットした値が出てくるので環境変数には正しく設定されているんだよな。。。
どう解決したか
最終的に、これはプロジェクトのルートディレクトリに .env を作ってそこに
GOOGLE_APPLICATION_CREDENTIALS=/home/.../credential.json
とセットし、main()の中で.envファイルを読み込むとエラーがでなくなりました。なぜかはわかりません。
- 作者:クラウドエース株式会社 吉積 礼敏・他
- 発売日: 2019/04/19
- メディア: 単行本（ソフトカバー）
Django で Chart.js を使ってグラフを描く
Django は Python を使うことで簡単に Web アプリケーションを作ることができることから非常に人気のあるフレームワークです。しかし、高度なアニメーションなどは Python だけでは表現することが難しく、JavaScript の力を借りることが多い印象を受けます。この記事では、グラフ描画でよく用いられる Chart.js を Django のプロジェクト内で使う方法について紹介したいと思います。特に、Python 側で処理したデータを JavaScript に渡して、Chart.js で描画するという部分について書きます。
開発環境
Django と Chart.js を結ぶ django-chartjs というライブラリがありますが、正直ここまでやらなくていいという感じを受けたので今回はこのライブラリ無しで実装を進めます。
準備
Django プロジェクトの準備はこれまでに何度か書いていますので、割愛します。詳しく知りたい方は以下の記事の「準備」までを参考にして作ってみてください。
pyhaya.hatenablog.com
Chart.js を使ってみる
ひとまず、Django の存在は最初にはできるだけ意識せず、HTML と JavaScript を使って適当なグラフを作ってみます。
{% load static %}
<html lang="ja">
<header>
<meta charset="utf-8">
<script src="https://cdnjs.cloudflare.com/ajax/libs/Chart.js/2.7.2/Chart.bundle.js"></script>
<script type="text/javascript" src="{% static 'visualize/js/draw.js' %}" defer></script>
</header>
<body>
<div style="width: 50%; heigh: 50%;">
<canvas id="graph"></canvas>
</div>
</body>
</html>
グラフだけを表示する HTML です。JavaScript のコードは
var ctx = document.getElementById("graph"); var myLineChart = new Chart(ctx, { type: "line", data: { labels: [ "Jan.", "Feb.", "Mar.", "Apr.", "May", "Jun.", "Jul.", "Aug.", "Sep.", "Oct.", "Nov.", "Dec." ], datasets: [ { data: [1, 2, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121], borderColor: "salmon", backgroundColor: "rgba(0,0,0,0)", }, ], }, options: { title: { display: false, }, scales: { yAxes: [ { ticks: { suggestedMax: 130, suggestedMin: 0, stepSize: 10, callback: function (value, index, values) { return value; }, }, }, ], }, }, });
x軸を labels に書いて、y軸の値を dataset に書いて、それ以外の軸の設定を options に書くというチュートリアルに載っていそうなコードです。
Django からデータを渡してグラフを描画する
では次に、Django からデータをもらってグラフを書くということをしてみます。これはユーザーがなにか操作をしてグラフを更新するような状況で、グラフにプロットされている値が不変でない状況です。
Django では HTML には context という形でデータを渡すことができます。そのため、JavaScript のコードを HTML 内の script タグの中に全部入れるという解決策がまず思い浮かびます。しかし、JavaScript のコードが長くなると、ソースコードがごちゃごちゃになってしまいます。そこで、データを JavaScript の変数に受け渡すところだけ script タグ内に入れるようにすればコードはスッキリします。
{% load static %}
<html lang="ja">
<header>
<meta charset="utf-8">
<script src="https://cdnjs.cloudflare.com/ajax/libs/Chart.js/2.7.2/Chart.bundle.js"></script>
<script type="text/javascript" src="{% static 'visualize/js/draw.js' %}" defer></script>
<script type="text/javascript">var data = {{ data }}</script>
</header>
<body>
<div style="width: 50%; heigh: 50%;">
<canvas id="graph"></canvas>
</div>
</body>
</html>
var data = {{ data }} で Django から JavaScript へデータの受け渡しが行われます。
var ctx = document.getElementById("graph"); var myLineChart = new Chart(ctx, { type: "line", data: { labels: [ "Jan.", "Feb.", "Mar.", "Apr.", "May", "Jun.", "Jul.", "Aug.", "Sep.", "Oct.", "Nov.", "Dec." ], datasets: [ { data: data, // ここで data を使っている borderColor: "salmon", backgroundColor: "rgba(0,0,0,0)", }, ], }, options: { title: { display: false, }, scales: { yAxes: [ { ticks: { suggestedMax: 130, suggestedMin: 0, stepSize: 10, callback: function (value, index, values) { return value; }, }, }, ], }, }, });
肝心の Python コードは
views.py
from django.shortcuts import render from django.views import View # Create your views here. class Index(View): def get(self, request): context = {"data": [i*i for i in range(12)]} return render(request, "visualize/index.html", context)
です。これで画面をリフレッシュすると先程のグラフと同様のグラフが表示されます。
GraphQL から GitHub API を叩く
最近、GitHub API を使ってリポジトリ情報を取ることが多いのですが、REST API より GraphQL を使ったほうが必要な情報だけを一気に取れるということを耳にし、試してみることにしました。
Query を作成
GraphQL はクエリの書き方が特殊なので REST API を普段使う人にとっては最初とっつきにくい感じを受けます。最初に指定できるのは Query という分類をされているもので、GitHub API のドキュメントに一覧が載っています。
この中から欲しい情報を選ぶのが最初のステップです。ここでは user にしてみましょう。上のリンクの一番下に userの説明があります。変数として login のみを指定できるようですね。これは String 型です。試しに私の情報を取ってみます。
{
user(login: "Hayashi-Yudai")
}指定できました。これだけでは実行しても指定した情報が足りずエラーが出てしまいますので情報を追加していきます。user は User型を返すと書いてある（user の横に青文字で User と書いてある）のでリンクをクリックして User 型がどのような情報をもっているのか見てみます。
commitComments や followers など色々あります。issuesというのがあるのでこれを取ってみましょう。引数として firstが取れるのでこれを10にして最初の10個を取ってみます。
{
user(login: "Hayashi-Yudai") {
issues(first: 10)
}
}issues の中には edgesやnodesなどが入っています。こんな調子でどんどん深くまでたどっていくと、
{
user(login: "Hayashi-Yudai") {
issues(first: 10) {
nodes {
body
}
}
}
}というクエリを書くことができます。一番深いところにある body は型が String なのでこれ以上深いところには何もありません。
Query を実行する
では最後に上で作成したクエリを Python で実行してみます。
import requests import os headers = {"Authorization": f"Bearer {os.environ.get('GITHUB_TOKEN')}"} def run(query): request = requests.post( 'https://api.github.com/graphql', json={'query': query}, headers=headers ) if request.status_code == 200: return request.json() else: raise Exception(f"Query failed to run by returning code of {request.status_code}. {query}") query = """ { user(login: "Hayashi-Yudai") { issues(first: 10) { nodes { body } } } } """ result = run(query)
GitHub Access Token は私の場合には環境変数に指定しているので os.environ.getで取ってきてヘッダに入れています。result の中身を見てみると
{'data': {
'user': {
'issues': {
'nodes': [
{'body': 'When I run some codes, text garbling happened. I tried hello world program by\r\n\r\n* Python3\r\n* Java\r\n* C\r\n* C++ \r\n\r\nbut, only in C and C++, text garbling happened.'},
{'body': 'In HTML, the width of `th` component is assigned like "5%", but it does not reflected in the page.'},
{'body': 'add regularization and batch-normalization to transposed convolution layer'},
{'body': 'add the pooling layer'},
{'body': 'create UNet by components I prepared.'},
{'body': 'To training UNet model, I should change input images to one-hot representation'},
{'body': 'create training session'},
{'body': 'To evaluate the model, I should set metrics such that accuracy or loss'},
{'body': 'show training result as images'},
{'body': 'To split training and validation of the model, I should give the is_training parameter when running the session.'}
]
}
}
}}これを見てみると user -> issues -> nodes -> body という構造になっていてクエリで書いた構造と同じ構造でレスポンスが返ってきていることが分かります。
Django でログインページを作る
Python のフルスタックWebフレームワークとして有名な Django を使ってログインページを簡単に作ってみます。
準備
雛形の生成
Django のプロジェクトをセットアップします。
$ mkdir myapp $ cd myapp $ django-admin startproject config . $ python manage.py startapp myauth $ python manage.py startapp appmain $ python manage.py makemigrations $ python manage.py migrate $ python manage.py createsuperuser # ユーザー名とパスワードを設定する
これらを実行することで以下のようなディレクトリ構成が得られます。
$ tree -L 2
.
├── appmain # 内部ページ
│ ├── __init__.py
│ ├── admin.py
│ ├── apps.py
│ ├── migrations
│ ├── models.py
│ ├── tests.py
│ ├── views.py
├── config # プロジェクト全体の設定
│ ├── __init__.py
│ ├── asgi.py
│ ├── settings.py
│ ├── urls.py
│ └── wsgi.py
├── db.sqlite3
├── manage.py
└── myauth # 今回ログインページをつくるところ
├── __init__.py
├── admin.py
├── apps.py
├── migrations
├── models.py
├── tests.py
└── views.py
基本的な設定
config/settings.py
# ... LOGIN_REDIRECT_URL = "/" # ログイン後にどこに飛ばすか LOGIN_URL = "/myauth" # ログインページの URLを設定 # ... INSTALLED_APPS = [ "myauth.apps.MyauthConfig", # <- 追加 "appmain.apps.AppmainConfig", # <- 追加 "django.contrib.admin", "django.contrib.auth", "django.contrib.contenttypes", "django.contrib.sessions", "django.contrib.messages", "django.contrib.staticfiles", ] # ...
config/urls.py
from django.contrib import admin from django.urls import path, include urlpatterns = [ path("admin/", admin.site.urls), path("", include("appmain.urls")), path("myauth/", include("myauth.urls")), ]
appmain/urls.py
from django.urls import path from appmain import views urlpatterns = [path("", views.index, name="index")]
myauth/urls.py
from django.urls import path from myauth import views app_name = "myauth" urlpatterns = [path("", views.Login.as_view(), name="login")]
内部ページの実装
ログインしたあとに飛ぶページを作ります。これは今回の主題ではないので簡単に作ります。上の appmain/urls.py に設定したように、ルートページとして views.index を表示するようにしているので、これを作ります。
appmain/views.py
from django.shortcuts import render from django.contrib.auth.decorators import login_required @login_required def index(request): return render(request, "appmain/index.html")
呼ばれたら index.html を表示するだけです。シンプルですね。
appmain/templates/appmain/index.html
<html> <head></head> <body>This is inner page</body> </html>
Django では HTML ファイルは慣習的に (app名)/templates/(app名)/ ディレクトリに入れるということになっていますので少しパス名が長くなります。
ログインページの実装
まずはログイン情報を入力するフォームを作ります。
myauth/forms.py
from django.contrib.auth.forms import AuthenticationForm class LoginForm(AuthenticationForm): def __init__(self, *args, **kwargs): super(LoginForm, self).__init__(*args, **kwargs)
Django には認証用のフォームを作るためのクラスが用意されているのでそれを継承すれば良いです。このフォームをビューに組み込みます。
myauth/views.py
from django.contrib.auth.views import LoginView from myauth.forms import LoginForm class Login(LoginView): form_class = LoginForm template_name = "myauth/index.html"
これでログインページの実装は９割方終わりです。あとは HTML ファイルを作ります。
myauth/templates/myauth/index.html
<html>
<head>
<title>Login Page</title>
</head>
<body>
<h2>Login</h2>
<form method="post" action="{% url 'myauth:login' %}">
{% csrf_token %}
{{ form.username }}
{{ form.password }}
{% if form.errors %}
<p>ユーザー名またはパスワードが一致しません</p>
{% endif %}
<input type="submit" value="login"/>
</form>
</body>
</html>
ビューの中でフォームを取り込んでいるので、HTML内では LoginFormの持つ変数を使うことができます。この記事では明示的にフォーム内で変数を定義することはしていませんが、AuthenticationForm が usernameとpasswordを定義しているのでそれを HTML 内で {{ form.username }}のようにして使うことができます。
フォームのアクションとして myauth:loginを指定しています。これは「myauth」という名前空間内の「login」というビューにフォームの内容を送信するということを指定しています。「myauth」の urls.py 内を見直してみると
path("", views.Login.as_view(), name="login")
という記述があります。myauth:login の login は、この name="login" を指しています。
実行してみる
では、今まで実装してきたコードを試してみます。
$ python manage.py runserver
として http://localhost:8000/myauth にアクセスしてみます。
CSS は何も書いていないので非常にシンプルですがきちんとログインページが出来ています。一番最初に管理者としてユーザーを１人登録していますのでそのユーザーのユーザー名とパスワードを入力すれば内部ページに飛べます。間違っていれば ユーザー名またはパスワードが一致しません という文字が表示されるはずです。
Python から PostgreSQL を操作する
Python はデータの解析で使われることが多く、様々な記事で解析の方法や結果の可視化手法が紹介されています。多くの記事では構造化データを扱う例として CSV を pandas を使って解析していますよね。しかし、扱うデータが非常に多い場合にはデータベースを叩いてほしいデータを取り出して解析するということも往々にして行われています。この記事ではデータベースとして有名な PostgreSQL を、Python から操作する方法について紹介したいと思います。
動作環境
- Ubuntu 20.04
- Python 3.8.2
- PostgreSQL 12.4
データベースの準備
PostgreSQL の Ubuntu へのインストールは以下の記事を参考にしました。
Debian用の記事ですが apt install を使うだけなので問題はありませんでした。無事インストール出来たか確認します。
psql -V # psql (PostgreSQL) 12.4 (Ubuntu 12.4-0ubuntu0.20.04.1)
上のようにバージョンがちゃんと表示されていればOKです。次にデータベースを１つ作ります。
createdb mydb
psql mydb # 接続確認
mydb=>\l # 存在するデータベースのリストを表示
List of databases
Name | Owner | Encoding | Collate | Ctype | Access privileges
-----------+----------+----------+-------------+-------------+-----------------------
mydb | pyhaya | UTF8 | ja_JP.UTF-8 | ja_JP.UTF-8 |
postgres | postgres | UTF8 | ja_JP.UTF-8 | ja_JP.UTF-8 |
template0 | postgres | UTF8 | ja_JP.UTF-8 | ja_JP.UTF-8 | =c/postgres +
| | | | | postgres=CTc/postgres
template1 | postgres | UTF8 | ja_JP.UTF-8 | ja_JP.UTF-8 | =c/postgres +
| | | | | postgres=CTc/postgres
テーブルは Python で作ることもできますが、1回しか実行しないものなので SQL でやっておきます。
CREATE TABLE repo ( id INTEGER, node_id VARCHAR(100), name VARCHAR(100), full_name VARCHAR(100), owner VARCHAR(100), private BOOLEAN, PRIMARY KEY(id) );
このテーブルは後に GitHub API を使ってリポジトリの情報を取ることを想定しています。APIの使い方は下のリンクを参考にしてください。
docs.github.com
この SQL を実行するには
mydb=>\i create_table.sql
とします。
Python から PostgreSQL を操作する
import psycopg2 import dotenv import os import requests from requests.auth import HTTPBasicAuth def get_repos(): auth = HTTPBasicAuth( os.environ.get("GITHUB_USERNAME"), os.environ.get("GITHUB_TOKEN") ) data = requests.get("https://api.github.com/users/(USER_NAME)/repos", auth=auth) data = data.json() return data[0] def connect(user, dbname, password): return psycopg2.connect( " user=" + user + " dbname=" + dbname + " password=" + password ) if __name__ == "__main__": dotenv.load_dotenv() user = "pyhaya" dbname = "mydb" password = os.environ.get("PG_PASSWORD") data = get_repos() ID = data["id"] node_id = data["node_id"] full_name = data["full_name"] owner = data["owner"]["login"] private = data["private"] query = ( "INSERT INTO repo (id, node_id, full_name, owner, private) VALUES" + f" ({ID}, '{node_id}', '{full_name}', '{owner}', {private});" ) with connect(user, dbname, password) as conn: with conn.cursor() as cur: cur.execute(query) conn.commit()
データベースへの接続のために with を使っています。これを使わずに操作の終了後にコネクションを connect.close()のようにすることもできますが、withを使ったほうが安全なのでこちらを使うようにします。
ちゃんとデータベースに入ったか確認してみます。
mydb=> SELECT id, node_id, full_name, owner, private FROM repo;
id | node_id | full_name | owner | private
-----------+----------------------------------+-----------------------------+---------------+---------
251618774 | MDEwOlJlcG9zaXRvcnkyNTE2MTg3NzQ= | pyhaya/analysis_memo | pyhaya | f
(1 row)
ちゃんと入っていることが確認できました。
AtCoder Beginners Contest 128 C. Switches を解いたのでメモ
久しくブログを更新していなかった気がするので、AtCoder の過去問を解いた記録でも書いてみる。AtCoder Beginners Contest (通称 ABC) 128 の C 問題を解いてみたら再帰関数の良い練習になったのでこれを紹介します。
問題文は下のリンクを参照。
解く方針
問題文を読んで最初に思ったのが、変数が多いということ。N がスイッチの数で M が電球の数、k が各電球につながっているスイッチの数で、sが各電球につながっているスイッチの番号、pが各電球の点灯条件。。。頭ごっちゃになりそう。変数の持ち方を考えるが、あまり深く考えずに N, M は int、s は多次元ベクトルでまとめて、p もベクトルとして持つことにする。
N, M も大きくなっても 10 までなのでスイッチの状態を全列挙してそれぞれの状態でスイッチが全部つくかどうかを調べることにする。
コード
Step 1
ということで早速、解答の雛形を書いてみる。
#include <bits/stdc++.h> typedef long long ll; using namespace std; int N, M; vector<vector<int>> info; int main() { // N: switch // M: light cin >> N >> M; vector<int> P(M); for (int i = 0; i < M; i++) { int k; cin >> k; vector<int> tmp(k); for (int j = 0; j < k; j++) { int a; cin >> a; tmp[j] = a - 1; } info.push_back(tmp); } for (int i = 0; i < M; i++) { cin >> P[i]; } vector<int> init_state(N, 0); // present state of switches int res = calc(0, P, init_state); cout << res << endl; }
このコードではデータの読み込みしか書いてない。具体的な計算は calc に丸投げしてる。書くことがあるとすれば電球の番号が1始まりで与えられていて扱いづらいので0始まりにしていることくらい (19 行目)。あとは N, M, info をグローバル変数にしていることくらいか。これは単純に calc にたくさん引数を与えるのが面倒という理由しか無い。
Step 2
calc 関数を書いていく。
int calc(int now_idx, vector<int> P, vector<int> now_state) { if (now_idx == N) { return is_valid(P, now_state); } vector<int> new_state; // state that 'now_idx'th switch is on. for (int i = 0; i < now_state.size(); i++) { if(i == now_idx) new_state.push_back(1); else new_state.push_back(now_state[i]); } return calc(now_idx + 1, P, now_state) + calc(now_idx + 1, P, new_state); }
よくある再帰関数の形。main() からは now_state として 0 のみを要素に持つベクトルが与えられる。これは全部のスイッチがoffである状態。スイッチの状態の総数は最初のスイッチが off の場合と on の場合の和になることを利用している。終端条件は、最後のスイッチの on/off を決めた時でこのときに return 1; とすれば単純にスイッチの状態の総数が返るようになる。しかしこの問題では状態に条件がついていて、このスイッチの状態で全ての電球が点灯していなければならない。なのでここでは単純に 1 を返さずにもうワンステップ噛ませる。この判定は is_valid に任せる。
Step 3
int is_valid(vector<int> P, vector<int> state) { // P: how to turn on the lights map<int, int> search; for (int i = 0; i < state.size(); i++) { if (state[i] == 1) search[i] = 1; } vector<int> P_copy; copy(P.begin(), P.end(), back_inserter(P_copy)); for (int i = 0; i < M; i++) { for (int j = 0; j < info[i].size(); j++) { if (search[info[i][j]]) P_copy[i] = !P_copy[i]; } } int count = 0; for (int i = 0; i < P_copy.size(); i++) { if (P_copy[i] == 0) count++; } return count == P.size(); }
各電球について、つながっているスイッチの中で on になっている数を数えてそれを２で割ったあまりが点灯条件を満たすか調べる。１つ１つの電球に対してつながっているスイッチの on/off をベクトルから調べるのは面倒なので最初に search というマップにして持つ。
あとは「on になっている数を数えてそれを２で割ったあまりが点灯条件を満たすか調べる」部分だが、これも簡単にかけないか考えると、P の値を スイッチが on であるたびに 0, 1 反転させて 0 になっていればその電球はついていることに気づく。どういうことかというと、ある電球が on になっているスイッチが奇数のときにつくとすると、この電球に対応する p の値は 1 である。この電球につながっている3つのスイッチが on になっているとして p を 3 回反転させると 0 になる。2回なら 1 になる。逆にスイッチの数が偶数のときに電球がつくとするとp = 0 で、２つのスイッチが on になっている状態では p を２回反転させると 0、3つだと 1 になる。つまり電球のつく条件がどちらでも on になっているスイッチの数だけ p の値を反転させるたときに p が 1になっていれば消えているし、0 になっていればついている。これをコードにしているのが 13 行目。
全体のコード
以上のコードをまとめると下のようになる。
#include <bits/stdc++.h> typedef long long ll; using namespace std; int N, M; vector<vector<int>> info; int is_valid(vector<int> P, vector<int> state) { // P: how to turn on the lights map<int, int> search; for (int i = 0; i < state.size(); i++) { if (state[i] == 1) search[i] = 1; } vector<int> P_copy; copy(P.begin(), P.end(), back_inserter(P_copy)); for (int i = 0; i < M; i++) { for (int j = 0; j < info[i].size(); j++) { if (search[info[i][j]]) P_copy[i] = !P_copy[i]; } } int count = 0; for (int i = 0; i < P_copy.size(); i++) { if (P_copy[i] == 0) count++; } return count == P.size(); } int calc(int now_idx, vector<int> P, vector<int> now_state) { if (now_idx == N) { return is_valid(P, now_state); } vector<int> new_state; for (int i = 0; i < now_state.size(); i++) { if(i == now_idx) new_state.push_back(1); else new_state.push_back(now_state[i]); } return calc(now_idx + 1, P, now_state) + calc(now_idx + 1, P, new_state); } int main() { // N: switch // M: light cin >> N >> M; vector<int> P(M); for (int i = 0; i < M; i++) { int k; cin >> k; vector<int> tmp(k); for (int j = 0; j < k; j++) { int a; cin >> a; tmp[j] = a - 1; } info.push_back(tmp); } for (int i = 0; i < M; i++) { cin >> P[i]; } vector<int> init_state(N, 0); // present state of switches int res = calc(0, P, init_state); cout << res << endl; }
![プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～](https://m.media-amazon.com/images/I/41oruV+aJIL._SL160_.jpg "プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～")
Union Find 木の実装
最近 AtCoder の過去問を解いていて、Union Find 木を使うと解くことができる問題に出会いました。これまで Union Find 木は使ったことがなく、聞いたことがあるくらいだったのでこの問題を解くために勉強しました。この記事では Union Find 木がどのようなデータ構造で、どんなことに使えるのかを説明したいと思います。
Union Find 木はどんなデータ構造か
名前にあるように、 Union Find 木は木構造です。つまり、親要素があって、それに連なる子要素がいくつかあるような構造をしています。木構造として有名なものに二分木やそれの特殊なものとしての二分探索木などがありますが、これらに対して Union Find 木は複数の木構造の集合からなるという特徴があります。
同じ木に属している要素は「同じグループ」に属していると解釈されます。つまり Union Find 木は特定の要素が他の要素と同じグループに属しているかどうかを判定するのに適しています。
Union Find 木の実装
Union Find 木を C++ で実装してみます。
struct UnionFind { vector<int> par; UnionFind(int N) : par(N) { for (int i = 0; i < N; i++) par[i] = i; } int root(int x) { if (par[x] == x) return x; return par[x] = root(par[x]); } void unite(int x, int y) { int rx = root(x); int ry = root(y); if (rx == ry) return; par[rx] = ry; } bool same(int x, int y) { return root(x) == root(y); } };
UnionFind という名前の構造体を定義します。この構造体は par という要素をもっており、par はそれぞれの要素の親要素をもっています。
初期化
簡単のために考える要素は0 ~ N-1 までの連続する整数であるとして話を進めます。最初に、Union Find 木を初期化するときには全ての要素の親要素が自分自身 (par[i] = i) になるように初期化します。
一番上の親要素の取得
特定の要素の属する木の最も上にいる親要素を取得するメソッドを定義します。par[x] で x と直接つながっている親を取得できるので、これを再帰的にたどっていけば一番上の親に到達できます。
要素の結合
要素 x と要素 y が同じグループに属するとして結合します。x 属する木に y を結合するとして話を進めていきます。これは非常に簡単で、 y の親を x の親にすればよいです。
2つの要素が同じグループに属するか判定
2つの要素の一番上の親が同じかどうかを判定すればいいだけです。
![プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～](https://m.media-amazon.com/images/I/41bHxtpurqL._SL160_.jpg "プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～")
