BEATBIT (UVa Live Archive Europe - Southwestern - 2007/2008 Lisbon (Portugal))

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3981

問題

分岐、ジャンプ、リターン0、リターン1の4命令で作られるプログラムが2つある。その2つのプログラムにどのような入力をしても同じ出力を返すか。
スタックの深さは最大128
コードの長さは最大10000

解法

プログラムの分岐命令をグラフに直して http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4610 と同じようにグラフを圧縮してやればよい。
グラフの圧縮は左の子、右の子の値によって親の値を決定させ、同じような頂点があればその値と同じ値にしておき、それを再帰的に適用させれば良い。