再帰関数を使わずにlowlinkを求める。
全変数を保存しないで再帰をstack使って書き換える方法ってありますか
— hogloid@へなちょこさん (@hogloid) 2013年2月3日
@the_nikaidoes 深さが10^5,6になる再帰関数をstackで書きなおすとき、for文で回している変数や戻り値を含む関数内のすべての変数を保存しないと自分はstackに直せなくて、面倒だなーと
— hogloid@へなちょこさん (@hogloid) 2013年2月3日
@the_nikaidoes 迷路だと頂点訪れる順番とか関係無い&関数呼び出した後は何もしないので楽ですが、僕がさっきやってたlowlinkを求めるモノとかは関数呼び出してからも処理があるので、なかなか大変
— hogloid@へなちょこさん (@hogloid) 2013年2月3日
こんな会話がありまして、パズルみたいで面白そうだと思ってちょっとやってみました。(lowlinkとかの解説)
コードはここです。
「状態(今いる頂点,今見てる辺)を頂点にした探索木を考えれば、あとは迷路の時と同じ要領」って感じでしょうか。