[백준] 숫자고르기

https://www.acmicpc.net/problem/2668

2668번: 숫자고르기

 

사이클을 만족하면 그 수는 구하고자 하는 집합의 원소가 될 수 있다.(최대로 많이 뽑아야 하기 때문이다.)

또한, 집합의 원소라면 사이클이기 때문에 필요충분조건을 만족하여 해당하는 수를 구하면 된다.

 

예제 입력을 예로 들면,

1 -> 3 -> 1 : 1이 사이클을 만족하므로 3 또한 사이클을 만족한다.

2 -> 1 -> 3 -> 1 : 2는 사이클을 만족하지 않으므로 집합의 원소가 될 수 없다.

 

import sys

N = int(sys.stdin.readline())
table = [0] * (N + 1)

for i in range(1, N + 1):
    table[i] = int(sys.stdin.readline())

answer = [0] * (N + 1)

for i in range(1, N + 1):
    if answer[i] == 0:
        k = i
        s = set()
        s.add(i)

        while i != table[k]:
            k = table[k]
            l = len(s)
            s.add(k)

            if l == len(s):
                break

        if i == table[k]:
            for j in s:
                answer[j] = 1

print(sum(answer))

for i in range(1, N + 1):
    if answer[i] == 1: print(i)