백준 2668 숫자 고르기 python

문제 링크: 숫자 고르기

개념 정리
DFS의 의미는 연결요소!
우리는 DFS를 이용해서 연결요소의 크기/개수를 구할 수 있고, 연결 요소의 정보에 대해 알 수 있다.

배운 것

• DFS를 이용해 싸이클 확인 법.

문제 해설

첫째 줄 수를 뽑았을 때 집합이
뽑힌 수들의 밑에 있는 수들의 집합과 일치하는 걸 찾는 게 목표!

그림을 그려보면 다음과 같다.

1 - 3 을 뽑으면 일치
5를 뽑으면 일치
즉, 집합이 일치 하기 위해선
싸이클이 있는 것을 찾으면 된다.

def DFS(x, idx):
   visit[x] = True
   for y in adj[x]:
       if visit[y] and y == idx:
           cycles.append(idx)
       if visit[y]: continue
       DFS(y, idx)


N = int(input())
adj = [[] for _ in range(N+1)]
cycles = []
for i in range(1, N+1):
   adj[i].append(int(input()))
for i in range(1, N+1):
   visit = [False] * (N+1)
   DFS(i, i)
print(len(cycles))
print(*cycles, sep='\n')