木上のアルゴリズム

研究中に練習問題としてちょうどいいレベルの問題がいくつかでてきたのでメモ．
全部簡単だけど，きれいなプログラムにするのは悩む．
問1,3は線形時間でメモリはO(1)
問2,4は線形時間で線形メモリ

まずはnotation

[n]={0,1,2,..,n}
f: [n]->[n]
f(k)0), f(0)=0
f^*(k)={k, f(k), f(f(k)), f(f(f(k))), ...}

• 問1

k∈[n]が与えられたとき，f(s)=kなるsが存在するかを判定するアルゴリズム，

• 問2

f^*(k)の要素数が最大となるkを1つ求めるアルゴリズム．

• 問3

s,t ∈ [n]が与えられたとき，max{f^*(s)∩f^*(t)}を求めるアルゴリズム

• 問4

各列がちょうど2個の非ゼロ成分を持つZ_2上の n x (n+1)行列が疎行列表現で与えられたとき，
ランクがnであるかを判定するアルゴリズム．

すなわち，無向グラフが接続リストで与えられたとき，全域木であるかどうかを判定する問題