Freshman's Database

#include <stdio.h>
#include <iostream>
#include <memory.h>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

#define sqr(a) ((a) * (a))
#define pi 3.1415926535897932384626433832795

#define TASK "f"
//#define CONTEST 1
#define MAXN 1000005
#define MAXE 2000005

int fst[MAXN], nxt[MAXE], en[MAXE];
int was[MAXN];
int cnt;
int cycles;
int n;


void AddEdge(int a, int b)
{
	nxt[cnt] = fst[a];
	fst[a] = cnt;
	en[cnt] = b;
	cnt++;	
}

void dfs(int x)
{
	was[x] = 1;

	for(int i = fst[x]; i != -1; i = nxt[i])
	{
		if(was[en[i]] == 0)
			dfs(en[i]);
		else
		{
			if(was[en[i]] == 1) cycles++;
		}
	}	

	was[x] = 2;
}

void Load()
{
	cin >> n;

	for(int i = 1; i <= n; i++)
	{
		int p;
		cin >> p;
		AddEdge(i, p);
	}
}

void Solve()
{
	for(int i = 1; i <= n; i++)
		if(was[i] != 1) dfs(i);

	cout << cycles;
}

int main()
{
#ifdef CONTEST
	freopen(TASK".in", "r", stdin);
	freopen(TASK".out", "w", stdout);
#endif
	memset(fst, -1, sizeof(fst));
	Load();
	Solve();

	return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED