https://www.acmicpc.net/problem/9466
시간 3초, 메모리 256MB
input :
- T
- n (2 ≤ n ≤ 100,000)
- 학생들의 번호(1 <= 학생 <= n)
output :
- 프로젝트 팀에 속하지 못한 학생들의 수
조건 :
-예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.
1 2 3 4 5 6 7
3 1 3 7 3 4 6
위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.
하.... ㅋㅋㅋㅋㅋㅋㅋㅋㅋ
일단 순열 사이클 문제와 매우 비슷하다.
문제를 풀 때 알아야 할 포인트는 이 문제도 사이클이 형성되는지를 보는 것이다.
루트 노드를 일관 되게 만들어 주듯 pivot을 일관되게 만들고.
함수를 끝내기 전, 다시 싸이클을 돌면서 루트 노드가 동일한 지 확인을 하는 것이다.
언제나 그렇듯 연습장에 루트 노드를 동일 하게 만드는 건 그리지만 다시 되돌아간다는 것을 생각 못해 시간을 썼다.....
어차피 싸이클이면, 마지막 끝나는 지점부터 다시 next_node를 찾아가도 연결이 되어야 하기에 바로바로 next_node를 찾으면 된다.
import sys
t = int(sys.stdin.readline())
for i in range(t):
n = int(sys.stdin.readline())
graph = [0] + list(map(int, sys.stdin.readline().split()))
visit = [0] * (n + 1)
for i in range(1, n + 1):
pivot = i
if visit[i] == 0:
# 연결되는 모든 노드들 일단 동일한 그룹으로 만들자.
while visit[i] == 0:
visit[i] = pivot
i = graph[i]
# 현재 i는 싸이클이 만들어 졌을 경우 최종 아이템이 들어있다.
while visit[i] == pivot:
visit[i] = -1
i = graph[i]
cnt = 0
for item in visit:
if item > 0:
cnt += 1
print(cnt)
