コンテンツにスキップ

DOJ Beginner Contest 12 D - Yet Another Hamiltonian Path Problem

サイト
DOJ
コンテスト
DOJ Beginner Contest 12
問題
D - Yet Another Hamiltonian Path Problem

頂点 1,…,N1, \dots, N の有向グラフがあり、各頂点 ii に Ai∈{0,1}A_i \in \{0, 1\} が与えられます。Ai=0A_i = 0 なら、すべての j<ij < i に対して辺 i→ji \to j があります。Ai=1A_i = 1 なら、すべての j>ij > i に対して辺 i→ji \to j があります。すべての頂点をちょうど 1 回ずつ通る経路(ハミルトン路)を 1 つ出力する問題です。存在しなければ −1-1 を出力します(2≤N≤5×1052 \le N \le 5 \times 10^5、全テストケースの NN の総和は 5×1055 \times 10^5 以下)。

Ai=0A_i = 0 の頂点を「左向き」、Ai=1A_i = 1 の頂点を「右向き」と呼びます。左向きの頂点どうしは番号の大きい順にたどれて、右向きの頂点どうしは番号の小さい順にたどれます。あとは、2 つの列をつなげられるかどうかです。

  • AN=0A_N = 0 のとき:右向きの頂点を小さい順にたどり、続けて左向きの頂点を大きい順にたどります。つなぎ目では、最後の右向きの頂点から左向きの頂点 NN に進みます。NN はどの頂点より番号が大きいので、この辺はあります。
  • A1=1A_1 = 1 のとき:左向きの頂点を大きい順にたどり、続けて右向きの頂点を小さい順にたどります。つなぎ目では、最後の左向きの頂点から右向きの頂点 11 に進みます。11 はどの頂点より番号が小さいので、この辺はあります。
  • A1=0A_1 = 0 かつ AN=1A_N = 1 のとき:頂点 11 は左向きなのに自分より小さい頂点がなく、頂点 NN は右向きなのに自分より大きい頂点がありません。どちらも出る辺がないので、経路の終点にしか置けません。終点は 1 つなので、ハミルトン路は存在しません。

計算量は O(N)O(N) です。

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 で −1-1 の場合を除いているので、else に来たときは A1=1A_1 = 1 です。