FortranでUnion-Findモジュールを使う

#FortranでUnion-Findモジュールを使う
この記事ではFortran90でUnion-Find木を使うための知識を共有していこうと思います。
以下のコードは私が実装したUnion-Findモジュールです。機能は初期化(init)、結合(unit)、根の番号を求める(root)を実装してあります。integer(8)を使っているので型に注意してください。1-indexedでの実装です。最後に使用例を載せました。

module UnionFind
	implicit none
	public
		type :: Union_Find
			integer(8),allocatable,dimension(:) :: par
		end type Union_Find
	contains
		subroutine init(p,n)
			implicit none
			type(Union_Find)  p
			integer(8) n,i
			allocate( p%par(n) )
			do i=1,n
				p%par(i) = i
			enddo
		end subroutine init
		recursive function root(p,n) result(ret)
			implicit none
			type(Union_Find) p
			integer(8) ret,n
			if(p%par(n)==n)then
				ret = n
				return
			else
				p%par(n) = root(p,p%par(n))
				ret = p%par(n)
				return
			endif
		end
		subroutine unite(p,a,b)
			implicit none
			type(Union_Find) p
			integer(8) a,b
			a = root(p,a)
			b = root(p,b)
			if(a/=b)then
				p%par(a) = b
			endif
		end
end module UnionFind

以下で使い方を説明していきます。

###1.useで読み込む
useで読み込むのを忘れないようしましょう。

use UnionFind

###2.宣言
以下のように宣言するとufという名前のUnion_Find型の変数が宣言されます。

type(Union_Find) uf

###3.初期化
callでinit関数を呼び出し、ufというUnion_Find型の変数をサイズN(integer(8)型なので注意)で初期化します。初期化は必ず行ってください。初期化は何度でもできます。

call init(uf,N)

###4.結合
callでunite関数を呼び出し、Union_Find型変数ufのa番目とb番目を結びます。

call unite(uf,a,b)

###5.根を求める
root関数で、Union_Find型変数ufのa番目の属する集合の根の番号を取得します。返り値はinteger(8)です。

root(uf,a)
#　↓使用例
if(root(uf,a)==root(uf,b))then
  処理
endif

##最後に
このコードに少し付け足すと、「頂点aの属するクラスタのサイズ」や「最大クラスタのサイズ」なども取得できます。最後に使用例です。
https://atcoder.jp/contests/abc097/submissions/3768108

参考
https://www.slideshare.net/chokudai/union-find-49066733/1