[백준][DFS] 2668.숫자고르기

2668.숫자고르기

 

• 내 풀이
  • 1,2번 행끼리의 집합이 동일해야 한다
    • 1번행을 인덱스, 2번 행을 val로 두기
    • dfs 돌면서 사이클 찾기
  • 최대 길이 이므로 사이클 끼리 더함
  • 앞 사이클에서 진행된 애들은 다시 체크할 필요 X
• 처음에 바보같이 이미 존재하는 값의 위치를 bisect_left로 찾아서 틀림
• 순서대로 들어가있는게 아니기때문에 index로 찾아야함

n=int(input())
lst=[0]+[int(input()) for _ in range(n)]
answer=[]

def dfs(val):
    global answer
    if val in picked:
        i=picked.index(val)
        answer+=picked[i:]
        return

    picked.append(val)
    dfs(lst[val])
    return

for idx, val in enumerate(lst):
    if idx==0: continue
    if idx in answer or val in answer: continue
    picked = []
    picked.append(idx)
    dfs(val)

answer=list(set(answer))
print(len(answer))
print(*sorted(answer), sep='\n')