DOJ Beginner Contest 12 D - Yet Another Hamiltonian Path Problem
頂点 の有向グラフがあり、各頂点 に が与えられます。 なら、すべての に対して辺 があります。 なら、すべての に対して辺 があります。すべての頂点をちょうど 1 回ずつ通る経路(ハミルトン路)を 1 つ出力する問題です。存在しなければ を出力します(、全テストケースの の総和は 以下)。
の頂点を「左向き」、 の頂点を「右向き」と呼びます。左向きの頂点どうしは番号の大きい順にたどれて、右向きの頂点どうしは番号の小さい順にたどれます。あとは、2 つの列をつなげられるかどうかです。
- のとき:右向きの頂点を小さい順にたどり、続けて左向きの頂点を大きい順にたどります。つなぎ目では、最後の右向きの頂点から左向きの頂点 に進みます。 はどの頂点より番号が大きいので、この辺はあります。
- のとき:左向きの頂点を大きい順にたどり、続けて右向きの頂点を小さい順にたどります。つなぎ目では、最後の左向きの頂点から右向きの頂点 に進みます。 はどの頂点より番号が小さいので、この辺はあります。
- かつ のとき:頂点 は左向きなのに自分より小さい頂点がなく、頂点 は右向きなのに自分より大きい頂点がありません。どちらも出る辺がないので、経路の終点にしか置けません。終点は 1 つなので、ハミルトン路は存在しません。
計算量は です。
Python
for _ in range(int(input())): N = int(input()) A = list(map(int, input().split())) if A[0] == 0 and A[-1] == 1: print(-1) continue ans = [] if A[-1] == 0: for i in range(N): if A[i] == 1: ans.append(i + 1) for i in reversed(range(N)): if A[i] == 0: ans.append(i + 1) else: assert A[0] == 1 for i in reversed(range(N)): if A[i] == 0: ans.append(i + 1) for i in range(N): if A[i] == 1: ans.append(i + 1) print(*ans)A は 0 始まりなので、頂点の番号は i + 1 です。最初の if で の場合を除いているので、else に来たときは です。