Freshman's Database

#include <bits/stdc++.h>
#define UNVISITED -1
#define BIGINT 1 << 25
#define _ ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0), cout.precision(15);
using namespace std;

typedef long long int64;
typedef pair<int, int> ii;

int dfsCounter, ans, numSCC;
vector<int> parent, dfs_num, dfs_low;
vector<bool> inStack;
stack<int> S;

void SCC(int p){
    dfs_num[p] = dfs_low[p] = dfsCounter++;
    S.push(p);     // Abuse useage of stack. If we have included <stack> header, we can't
    inStack[p] = true;      // use stack here.

    int q = parent[p];
    if(dfs_num[q] == UNVISITED) SCC(q);
    if(inStack[q])  dfs_low[p] = min(dfs_low[p], dfs_low[q]);

    if(dfs_low[p] == dfs_num[p]){
		int nNodes = 0;
        while(true){
            q = S.top();
            S.pop();
            inStack[q] = false;
            nNodes++;
            if(q == p)	break;
        }
        if(nNodes > 1)	ans++;
    }
}

int main(){ _
	int n;	cin >> n;
	dfsCounter = ans = numSCC = 0;
	parent.assign(n+1, UNVISITED);
	dfs_num.assign(n+1, UNVISITED);
	dfs_low.assign(n+1, UNVISITED);
	inStack.assign(n+1, false);
	for(int i = 1; i <= n; ++i)	cin >> parent[i];
	
	for(int i = 1; i <= n; ++i){
		if(dfs_num[i] == UNVISITED)
			SCC(i);
	}
	
	cout << ans << endl;
	
    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