functional graphとは
AtCoderのABCで以下のようなfunctional graphと呼ばれるグラフ構造の問題が出ることがある。
functional graph とは、各ノードから出ているエッジが1本のみである有効グラフのことで、ノード$u$からエッジを通して辿り着くノードを$f(u)$のように関数的に表せることからfunctional graphとよばれている。
このfunctional graphには、以下のような性質がある。
$Gの連結成分がK個あってC_1,C_2,…,C_K
とする。このとき、各連結成分には閉路が1つだけ存在する$
(引用:E - Takahashi's Anguish 解説 )
これは何を意味しているかというと、グラフ$G$をエッジによって連結しているか否かをチェックし$K$個に分割したとき、分割された各グラフ$G_k$内には閉路が1つのみ存在する、ということだ。
厳密な証明となるかは不明だが、もっと分かりやすく説明してみる。
元々のグラフ$G$はfunctional graphである故に、分割された各グラフ$G_k$も各ノードから1本しかエッジが出ていないのは共通しているのでfunctional graphである。したがって完全に連結しているfunctional graph内に閉路が1つだけ存在することを示せればよい。
例えば上図のグラフ構造の場合このように3つに分割できるわけだが、それぞれ場合分けして考えてみよう。
1. ノードが1つ
上図のノード7がそれに該当する。自分自身を指しているエッジが閉路に該当する。
2. ノードが2つ
上図のノード5,6がそれに該当する。それぞれのノードから互いのノードへ向かってエッジが出ているのでこれが閉路となる。
3. それ以上の場合
$G_k$にノードが$n$個ある場合、$n$個のノードが連結するのに最低限必要なエッジ数は植木算的に考えて$n-1$本である。
$G_k$に含まれるノードのうち$n-1$個のノードから出ている$n-1$本のエッジによってノードが連結されている場合(孤立しているノードがない場合)、ノードが直列的に繋がっている状態になるので残りの1つのノードから出ているエッジがどのノードに向かっていたとしても閉路が1つ出来上がる。
逆に$G_k$に含まれるノードのうち$n-1$個のノードから出ている$n-1$本のエッジによってノードが完全に連結されていない場合、残り1本を引くことによって完全に連結することが保証されているので孤立しているノードは高々1個である。このとき、連結状態にある$n-1$個のノードからなる部分グラフ中に閉路が1つあれば残りのエッジが孤立しているノードから連結部分に含まれるノードのいずれかに向かうことになるので、これも閉路が1つあるグラフ構造となる。
以下は上図のノード1~4に対してエッジが3本しかないケースについてシュミレートした例である。
したがって数学的帰納法よりfunctional graphには閉路がただ1つ存在することが示された。
本題
functional graphを競プロで扱う場合は、この性質に注目して実装することがおすすめである。
functional graph系の問題は最初に述べたようにどのノードからどのノードに辿り着くことができるのかを求める系の問題が多い。
このとき、分割された各グラフ$G_k$に含まれるノードが閉路に含まれるノードなのか否かによって場合分けをすることができる。
以下、疑似コードである
# G_kのノードiから辿り着くことのできるノードを見つけるコード
def find_dest_from(i):
if ノードiが閉路に含まれる:
return {G_k内の閉路に含まれるノード全て}
else:
return {i} + find_dest_from(iから出ているエッジが向かう先のノード)
このように、
- ノードが閉路に含まれている場合は、その閉路内のノードにしか辿り着けない
- 閉路外にノードがある場合は、閉路内のノードと閉路に辿り着くまでのパス上にあるノードに辿り着くことができる
ことを念頭に置いて実装していけばよい。
D-Teleporterの実装例
from collections import deque
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
A = [a-1 for a in A]
# 特定のノードiからの転移先jがf(i)で決まるとき、この有効グラフ構造をfunctional graphという。
# functional graphには閉路(ループ構造)が1つ存在することが既知として知られている
# queue構造を使うとよい。
queue = deque()
checked = [0] * N
# 末尾に追加するとき -> append
# 先頭から取り出すとき -> popleft, 末尾から取り出すとき -> pop
# 最初は0からのスタート
now = 0
while(checked[now]==0):
queue.append(now)
checked[now] = True
now = A[now]
# この時点でqueueはnowから到達可能な全ての点が入っている
while(K > 0 and queue[0]!=now):
# Kが十分に少ないときはK回移動して終わり
# Kが大きいときはループ構造を考慮する
K -= 1
queue.popleft()
if K==0:
# K回移動し終わったので終わり
print(queue[0]+1)
else:
# ループ構造を考慮、queueにはループ構造に含まれるノードが入っている状態
K %= len(queue)
print(queue[K]+1)
このように実装することでKがかなり大きい数だったとしても計算量を削減することができる。
E-Reachability in Functional Graphの実装例
from collections import deque
import numpy as np
from functools import cache
# functional graph : 各連結部分に閉路が1つだけ存在し、その他のノードはその閉路に連結している形状
N = int(input())
edge = list(map(int,input().split()))
edge = [e-1 for e in edge]
to_loop = [-1 for _ in range(N)] # ループ構造にかかるまでの距離
node_group = [-1 for _ in range(N)] # 連結部分ごとのフラグ
loop_count_per_group = [] # 各ノードグループ内の閉路に含まれるノードの数
node_group_count = 0
checked = [0] * N
for i in range(N):
if checked[i] == 1:
#i地点のnode_groupとto_loopが既に計算されている場合
continue
else:
now = i
dest_from_now = deque()
while(checked[now]==0):
checked[now] = 1
dest_from_now.append(now)
now = edge[now]
if to_loop[now] >= 0 and node_group[now] >= 0:
#now地点でnode_groupとto_loopが既に計算されている場合
while(dest_from_now):
j = dest_from_now.pop()
to_loop[j] = to_loop[now] + 1
node_group[j] = node_group[now]
now = j
else:
loop_count = 0
# ループ構造を格納
while(dest_from_now[-1]!=now):
j = dest_from_now.pop()
to_loop[j] = 0
node_group[j] = node_group_count
loop_count += 1
# nowの部分も考慮に
j = dest_from_now.pop() #= now
to_loop[j] = 0
node_group[j] = node_group_count
loop_count += 1
loop_count_per_group.append(loop_count)
# 残りの部分のto_loopとnode_groupを格納
while(dest_from_now):
j = dest_from_now.pop()
to_loop[j] = to_loop[now] + 1
node_group[j] = node_group_count
now = j
node_group_count += 1
# 各点が含まれる連結部分におけるループ構造に含まれるノード数の総和とループ構造に辿り着くまでのノード数を足し合わせる
print(np.dot(np.bincount(node_group),np.array(loop_count_per_group).T)+sum(to_loop))
こうすることで各ノードにつき1回しか訪問せずとも全てのノードから訪問できるノードの組を数えることができるので、$O(N)$で計算できる。
ちょっと難しい問題：E - Putting Candiesの実装例
from collections import deque
import numpy as np
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
# 最初はX = A[0]
# 2回目はX += A[X % N] (=A[A[0] % N])
# 3回目はX += A[X % N] (=A[(A[0] + A[A[0] % N]) % N])...
# X%Nのとりうる値は高々N個しかないので、どこかのタイミングで同じX%Nとなったら、それ以降はループする
X = 0
checked = [0] * N
loop_pick = deque()
while(checked[X % N] == 0 and K > 0):
loop_pick.append(X%N)
checked[X%N] = 1
X += A[X%N]
K -= 1
#print(K,X,loop_pick)
if K==0:
# Kが十分少ない場合はこの操作をやるだけで十分
print(X)
else:
#print(f"X%N={X%N}")
while(loop_pick[0]!=X%N):
loop_pick.popleft()
#print(loop_pick)
A = np.array(A)
X += np.sum(A[np.array(loop_pick)])*(K//len(loop_pick))
K = K%len(loop_pick)
#print(X,K,loop_pick)
while(K > 0):
i = loop_pick.popleft()
X += A[i]
K -= 1
#print(K,X,loop_pick)
print(X)
これはそもそもfunctional graph構造だと気づくのが難しい問題。$X (mod N)$の値は高々$N$個(0,1,...,N-1)しかないので、こういう余りを使って移動する系の問題は怪しいと思った方がいいかもしれない。入力例を使ってループ構造に入るかどうか実験してみて、途中でループっぽいところに入ったらfunctional graphだと予測しながら解くのがコツかも。