[Python/백준] 9466 텀 프로젝트

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

9466번: 텀 프로젝트

<문제 해설>

깊이 우선 탐색 문제이다. n번돌리면서 1번친구가 속할 곳이있는지...n번친구가 속할 곳이있는지 다 계산하면 시간 초과가 난다. 따라서 일반적인 dfs로 하면 안되고 한번이라도 팀계산에 참여했으면 방문했다고 기록해야한다.

1. 문제의 주어진 값들을 다 받는다. 방문을 했는지 기록할 visit배열을 만들어 준다.
2. n만큼 반복하면서 만약 n이 방문한 곳이 아니라면 n을 방문했다고 표시하고 n이 선택한 사람을 dfs인자로 넣어준다.
   또한 team에 n을 넣는다.
3. 함수 안에서는 선택한 사람들이 방문됐는지 확인하고 안됐으면 기록하며 재귀함수를 계속 해준다. 
   만약 방문이 된 선택된 사람이 나오면 team에 방문이 된 선택된 사람이 선택한사람이 있는지 확인하고(x라고하자) x다음으로 팀에 들어온 사람들은 팀만들기를 성공한거니 성공한 사람의 수를 count에 더해준다.
4. 총 사람수에서 성공한 사람수의 count를 빼서 출력해준다.

<코드>

def dfs(n):
    global count
    if visit[n] != 1:
        team.append(n)
        visit[n] = 1
        dfs(number[n]-1)
    else:
        I = len(team)
        for i in range(I):
            if team[i] == n:
                count += (I - i)

import sys
sys.setrecursionlimit(10**7)
T = int(sys.stdin.readline())
for t in range(T):
    N = int(sys.stdin.readline())
    number = list(map(int,sys.stdin.readline().split()))
    visit = [0]*N
    count = 0
    for n in range(N):
        if visit[n] != 1:
            team = [n]
            visit[n] = 1
            dfs(number[n]-1)
    print(N - count)