2668: 숫자고르기

문제 링크

2558: 숫자고르기

구현 방식

• 주어진 표를 단방향 그래프로 나타내주고, 해당 그래프를 순회하면서 사이클이 존재한다면 사이클의 원소들을 result set에 추가해주는 방식으로 구현해주었다
• 1차 for문을 돌면서 N번 dfs를 호출해줌
  • i가 result에 없는 경우에만 dfs를 호출해주고, 매번 visit 리스트를 선언해줌
• 참고사항: python에서 set 합집합 연산 -> result = result | tmp

코드

import sys
input = sys.stdin.readline

def dfs(idx, first, second):
    global result

    if visit[idx] == False:
        visit[idx] = True
        for num in graph[idx]:
            first.add(idx); second.add(num)
            if first == second:
                tmp = set(first); result = result | tmp
            dfs(num, first, second)

N = int(input())
graph = dict()
for n in range(1, N+1):
    m = int(input())
    if n in graph: graph[n].append(m)
    else: graph[n] = [m]

result = set()
for i in range(1, N+1):
    if i not in result:
        visit = [False] * (N+1)
        dfs(i, set(), set())

result = list(result); result.sort()
print(len(result))
for r in result: print(r)