문제
접근
알고리즘을 생각하기까지가 굉장히 어려웠다.
단순히 사이클을 검사하는 것을 넘어서, 사이클을 구성하는 노드들을 제외한 노드를 어떻게 찾을지 많이 고민했다.
특정 노드에 대해서 dfs를 수행하면서, 방문하는 노드들을 배열에 모두 담아두고 있는다. (반드시 순서대로!)
dfs를 수행하는 도중에 이미 방문한 노드가 등장한다면, 담아두었던 배열에서 해당 노드를 찾으면 된다!
예를 들어, 현재 방문 배열이 (1, 2, 4, 7) 이었다고 생각해보자.
그리고 4번 노드를 다시 왔다면, (4, 7)은 사이클을 이루고 있는 것이다.
(4, 7)은 사이클을 이루므로, 이를 제외한 (1, 2)는 팀에 속하지 않은 학생이 되는 것이다.
또한, 위의 (1, 2, 4, 7)의 dfs의 수행을 끝내고, 5번 노드에 대해 다시 dfs를 수행할 때,
5번 노드의 방문 배열이 (5, 6, 1) 을 이룬다고 생각해보자.
1은 이미 앞에서 방문한 노드이므로, (5, 6)은 사이클을 이룰수 없다.(이미 방문한 노드들에 대해서는 사이클 검사를 모두 수행했으므로)
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
T = int(input())
def dfs(v):
cycleMember = [v]
visit[v] = 1
while True:
v = choice[v]
if visit[v] == 0:
visit[v] = 1
cycleMember.append(v)
else:
if v in cycleMember:
return cycleMember.index(v)
else:
return len(cycleMember)
for case in range(T):
n = int(input())
choice = [0] + list(map(int, input().split(' ')))
visit = [0] * (n+1)
ans = 0
for i in range(1,n+1):
if visit[i] == 0:
visit[i] = 1
soloCnt = dfs(i)
ans += soloCnt
print(ans)