Small Groups (APCS 2017-03 Intermediate)

Points 100 1.0s 256M

There are \(N\) people numbered \(0,1,\ldots,N-1\). Each person writes down the number of their best friend. A person may write their own number if they have no other friend.

The written numbers form a permutation of \(0\) through \(N-1\): every number appears exactly once. Therefore, starting from any person and repeatedly moving to that person's best friend eventually returns to the starting point and forms a cycle. Everyone in the same cycle belongs to one small group.

For example, consider the following relationship for \(N=10\):

Person 0 1 2 3 4 5 6 7 8 9
Best friend 4 7 2 9 6 0 8 1 5 3

There are four small groups: \(\{0,4,6,8,5\}\), \(\{1,7\}\), \(\{3,9\}\), and \(\{2\}\).

Given everyone's best friend, determine the total number of small groups.

Input

The first line contains a positive integer \(N\), the number of people.

The second line contains \(N\) integers \(p_0,p_1,\ldots,p_{N-1}\), where \(p_i\) is the best-friend number written by person \(i\). These \(N\) values form a permutation of \(0\) through \(N-1\).

Constraints

  • \(1 \le N \le 50000\)
  • \(0 \le p_i < N\)
  • \(p_0,p_1,\ldots,p_{N-1}\) are pairwise distinct.
  • All input values are integers.

Output

Print one integer: the total number of small groups, followed by a newline. Do not print any extra text or spaces.

Scoring

The two sample cases are judged but worth 0 points. There are exactly \(20\) scored groups worth \(5\) points each:

  • Groups 01–04 (\(20\) points): \(1\le N\le100\), and every small group contains at most \(2\) people.
  • Groups 05–10 (\(30\) points): \(1\le N\le1000\), with no additional constraints.
  • Groups 11–20 (\(50\) points): \(1001\le N\le50000\), with no additional constraints.

Sample Input 1

10
4 7 2 9 6 0 8 1 5 3

Sample Output 1

4

Sample Explanation 1

The four groups are \(\{0,4,6,8,5\}\), \(\{1,7\}\), \(\{3,9\}\), and \(\{2\}\).

Sample Input 2

3
0 2 1

Sample Output 2

2

Sample Explanation 2

The two groups are \(\{0\}\) and \(\{1,2\}\).

Source

APCS March 4, 2017 implementation problem 2, “Small Groups.” Referenced from the official APCS problem PDF and ZeroJudge c291.

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.