ABC311 C - Find it! (Diff:448 茶) の解説 [AtCoder][Python]

問題へのリンク https://atcoder.jp/contests/abc311/tasks/abc311_c

問題概要

N頂点N辺の有向グラフがあり、i番目の頂点からはA[i]に伸びている。
この時、有向閉路を1つ求めよ。

入力例1

N = 7, A = [6, 7, 2, 1, 3, 4, 5]

入力例1のグラフ

画像:https://img.atcoder.jp/abc311/0ab396c54e276edb27de02ad3b20cf7f.png

出力例1

4
7 5 3 2

他の解答例
4
5 3 2 7

3
1 6 4

など

解き方

閉路とは、何度も同じ頂点をループする部分のこと。

入力例1では、試しに頂点1から辿ってみると、
1→6→4 → 1→6→4 → 1…と、何度も同じ頂点を回っていることがわかる。そして、この頂点の繰り返し(1, 6, 4)は求めたい閉路である。そのため、繰り返しが求められれば良い。

しかし、必ずしも最初から繰り返しになっているとは限らない。入力例3では、

入力例3のグラフ

画像:https://img.atcoder.jp/abc311/c31a7153e0ca36e8c0e1dd4c7bfe5329.png

1→3→4→ 7→8→2→ 7→8→2→ 7→8…と、(7,8,2)が途中からループになっている。そのため、

まず、訪れた頂点を管理する空のリストを作る
ある頂点から移動をスタートする。移動先の頂点が
- 初めて訪れた頂点であればそのリストに追加する
- もし訪れた頂点がリスト内にある(=既に訪れている)のなら、1回目の頂点がリストのどこにあるか探す→そこ以降の部分が閉路

というのを実装すれば答えが求められる。例えば入力例3では、リストに[1,3,4,7,8,2]と入れていき、その次の頂点は2回目の7で、その部分からはループになる。よって、閉路はリストにある1回目の7から、2回目の7が入る直前の2までであることが分かる。よって、答えはリストの1回目の7以降の部分[7,8,2]である。

ちなみに、開始する頂点はどこでもよく、必ずどこかの閉路に繋がっている。これは、頂点は必ずどこかに繋がっているので、頂点を移動する動作は無限に行われるが、頂点は有限個しかないので、最終的にはいずれかの閉路に繋がって無限ループしない限り動作を無限に行うことができないからである。

コード(Python)

N = int(input())
A = list(map(int,input().split()))
visited = [False] * (N+1) # 既に訪れたかを管理

L = []
x = A[1] # 今いる頂点を示すx
while not visited[x]: # xが訪れたことのある頂点になるまで
    L.append(x) # Lに追加
    visited[x] = True # 訪れた
    x = A[x-1] #次の頂点に移動

first_x = 0 #1つ目の頂点のindex
while L[first_x] != x:
    # xは2つ目の頂点を指す
    # 1つ目の頂点のindexを探す
    first_x += 1

ans_list = L[first_x:] # 答えはLのfirst_x以降
print(len(ans_list))
print(*ans_list)

8/2 文章を修正しました。