from collections import defaultdict
import sys
def dfs(key, visited):
if d[key] == start:
return visited
if d[key] not in visited:
visited.add(d[key])
return dfs(d[key], visited)
return False
n = int(input())
d = defaultdict(int)
for i in range(1, n+1):
d[i] = int(sys.stdin.readline().rstrip())
ans = []
for i in range(1, n+1):
start = i
result = dfs(start, set([i]))
if result:
ans.extend(result)
x = sorted(set(ans))
print(len(x))
for i in x:
print(i)
from collections import defaultdict
import sys
def dfs(key, visited):
if d[key] == start:
for v in visited:
ans.add(v)
if d[key] not in visited:
visited.add(d[key])
dfs(d[key], visited)
# return None
n = int(input())
d = defaultdict(int)
for i in range(1, n+1):
d[i] = int(sys.stdin.readline().rstrip())
ans = set()
for i in range(1, n+1):
start = i
dfs(start, set([i]))
x = sorted(list(ans))
print(len(x))
for i in x:
print(i)
시작한 KEY값으로 다시 돌아오는 싸이클을 가질 경우, visited
에 속하는 모든 KEY값들을 답에 추가한다.
from collections import defaultdict
import sys
def dfs(key, cycle):
visited[key] = True
if visited[d[key]]:
if d[key] in cycle:
left = cycle.index(d[key])
for c in cycle[left:]:
used.add(c)
else:
cycle.append(d[key])
dfs(d[key], cycle)
n = int(input())
d = defaultdict(int)
for i in range(1, n + 1):
d[i] = int(sys.stdin.readline().rstrip())
visited = [False] * (n+1)
used = set()
for start in range(1, n + 1):
if not visited[start]:
dfs(start, [start])
print(len(used))
for i in sorted(used):
print(i)
텀 프로젝트 문제와 동일한 풀이 방식이다.
주어진 N이 만만하다면 직관적인 2번째 풀이 코드를 사용해도 되지만, 텀 프로젝트 문제처럼 N이 큰 값으로 주어진다면 이 풀이를 사용하자.
싸이클 문제의 경우 key값으로 나타내지는 노드들은 단 한번만 방문하면 싸이클 여부를 판단할 수 있다.