[백준] 9466번 : 텀 프로젝트 with python3

12 Nov 2018

Reading time ~1 minute

문제: https://www.acmicpc.net/problem/9466

풀이

cycle count : cycle의 개수를 저장하는 곳
started: x가 어디에서 시작했는지를 알려주는 곳
- x에 연결된 다음노드가 default값
nexted : x의 연결된 위치 알려주는 곳

방문한 적 없는 모든 정점을 방문한다.
- 처음 방문한 정점은
- cycle_count에 길이를 저장한다.
- 그 정점이 어디에서 시작했는지 저장한다. - 이미 방문한 정점은
- 정점이 시작점과 다를경우 사이클이 x
- 만약 같다면 cycle인데 사이클이 아닌 정점까지 물릴 수 있어서
  - 사이클이 존재하는 정점을 인덱스로 활용
  - (탐색된 정점 개수 - 사이클 정점에 대한 길이)를 통해 사이클을 이루는 정점의 개수를 구한다

import sys
sys.setrecursionlimit(10**6)
input = lambda : sys.stdin.readline().strip()


def make_group(x, cnt, start): # start은 시작정점
    global nexted, cycle_count, started
    # 탐색할수록 정점의 개수(cnt)는 늘어간다.
    # nexted 배열에 탐색할때마다 해당 정점을 기준으로 탐색된 정점의 개수를 저장한다.

    while True:
        if cycle_count[x] != False: # 방문 이미 한 곳
            if start != started[x]: # 정점 시작점이 다를 경우 사이클 x
                return 0
            return cnt - cycle_count[x]
            # 그러던 중 사이클이 존재하면, 사이클이 존재하는 정점을 인덱스로 활용하는 것이다.
            # (탐색된 정점 개수 - 사이클 정점에 대한 길이)를 통해 사이클을 이루는 정점의 개수를 구하게 된다.

        cycle_count[x] = cnt
        started[x] = start
        x = nexted[x]
        cnt += 1

for _ in range(int(input())):
    n = int(input())
    cycle_count = [False]*(n+1)
    # cycle_count는 x에 도착했을 때 탐색한 개수를 저장하는 곳
    # started는 x가 어디에서 시작했는지를 알려주는 곳

    nexted = {}
    # x의 연결된 위치 알려주는 곳
    started = [0]+list(map(int, input().split()))
    for i in range(1, n+1):
        nexted[i] = started[i]

    ans = 0
    for i in range(1, n+1):
        if cycle_count[i] == False:
            ans += make_group(i, 1, i);

    print(n-ans)