주둔

• 정의된 효용성의 합을 다르게 세어보자. 어떤 부대가 있는 노드에서 인접한 노드들 중에서 부대가 없는 노드의 개수가 그 부대의 효용성이 된다. 그러므로 모든 효용성의 합은, 그래프의 엣지들 중에서 한쪽 끝에는 부대가 있고 다른쪽 끝에는 부대가 없는 엣지의 개수로 셀수도 있다.
• 그러면 각 노드에 T 또는 F의 값을 할당했을때, 양쪽 끝 노드의 값이 다른 엣지의 수가 최대가 되도록 값을 할당하는 방법을 생각해보자.
• 이분그래프라면 모든 엣지가 조건을 만족하도록 만들수 있다. 다시말해 주어진 그래프가 이분그래프라면 답은 엣지의 갯수인 N이 된다
• 이분그래프가 아니라면, 그래프가 홀수 사이클을 포함하고 있다는 말과 동치이다. 홀수 사이클들끼리 연결되어있는 경우가 없다면, 각 사이클마다 조건을 만족시키지 못하는 엣지가 1개씩 생기므로, 홀수 사이클의 개수만 세어주면 간단할것 같은데, 홀수 사이클들끼리 에지를 공유하는 경우들에는 계산이 좀 복잡해질것 같다.
• 하지만, 다행히도 이 문제에서 사용되는 그래프는 일반적인 그래프가 아니다. 전체 엣지의 갯수가 노드의 갯수와 동일하고, 커넥티드 컴포넌트 단위로 분리했을 때에도, 각 컴포넌트마다 엣지의 갯수와 노드의 갯수가 동일하게 된다. 결과적으로, 컴포넌트 단위로 분리하면, 컴포넌트마다 사이클을 1개씩만 갖게되고, 사이클들끼리 연결되는 경우는 없다.
• 그럼 이제 앞에서 말한대로, 홀수 사이클들의 개수를 세어주기만 하면 된다. 한가지 언급안한것은 사이클의 크기가 2인 경우인데, 이경우는 두 노드 사이에 중복 엣지가 있는 것과 같으므로 이 경우에도 한개를 빼줘야 한다.
• 그래서 답은 {전체 엣지의 개수} - {홀수 사이클의 개수} - {길이 2짜리 사이클의 개수} 가 된다. 컴포넌트로 분리하고, 컴포넌트에서 사이클을 찾아서 사이클의 길이의 홀짝여부를 계산하는 것까지 bfs나 dfs한번에 처리 가능하다. 시간복잡도는 O(n). 그래프의 특징을 활용하면, 일반적인 bfs나 dfs를 돌리기 위해 주어진 d배열을 일반 그래프 형태로 바꿀 필요도 없이, 그냥 바로 d배열을 따라서 탐색하면서 사이클을 찾아도 된다. 당연히 이쪽이 더 효율적이다

"""Solution code for "BOJ 31414. 주둔".

- Problem link: https://www.acmicpc.net/problem/31414
- Solution link: http://www.teferi.net/ps/problems/boj/31414

Tags: [graph]
"""


def main():
    N = int(input())
    d = [int(x) - 1 for x in input().split()]

    answer = N
    comp_no = [None] * N
    dist = [None] * N
    for source in range(N):
        if comp_no[source] is not None:
            continue
        cur = source
        for cur_dist in range(N + 1):
            if comp_no[cur] is not None:
                break
            comp_no[cur], dist[cur] = source, cur_dist
            cur = d[cur]
        if comp_no[cur] == source:
            length = cur_dist - dist[cur]
            if length == 2 or length % 2 == 1:
                answer -= 1

    print(answer)


if __name__ == '__main__':
    main()