Proficient.
Put your skills to the test.

Problem summary

The key of each of N locked piggy banks is inside another listed bank, possibly itself. Breaking a bank reveals all keys inside it; thereafter banks may be unlocked for free. Find the minimum banks to break to open every bank. Solve exactly two instances.

Constraints

1 ≤ N ≤ 100000 per instance; each key location is from 1 through N.

Worked example

An independently prepared example for this explanation.

4
2
1
2
4
3
3
3
3

2 1

Solution analysis

1. Draw an edge from each bank to the bank holding its key. Every vertex has one outgoing edge, so every weakly connected component contains exactly one directed cycle.
2. At least one bank on each cycle must be broken: its keys form a circular dependency with no key initially available. Conversely, breaking one cycle bank unlocks the whole cycle and then every tree feeding into it. The answer is therefore the number of components.
3. Use a disjoint-set structure and merge every bank with its key location. The number of remaining roots is the answer. The first sample has a component on 1,2,3 and a self-loop component at 4, requiring two breaks; the second needs only bank 3.

Why it works

A finite graph with one outgoing edge per vertex has exactly one cycle in each weak component. No key from outside a cycle can open a cycle bank, since each such bank’s unique key is on the cycle. One break per cycle is necessary, and following the revealed keys opens the entire component, so it is sufficient. Disjoint-set merging counts these components.

Watch out. The input gives where each key is located, not which key a bank contains. Exactly two test instances are required.

An independently written complete program with standard headers.

#include<iostream>
#include<numeric>
#include<vector>
using namespace std;
struct DSU{
    vector<int>parent,size;
    explicit DSU(int n):parent(n),size(n,1){
        iota(parent.begin(),parent.end(),0);
    }
    int find(int x){
        while(parent[x]!=x){
            parent[x]=parent[parent[x]];
            x=parent[x];
        }
        return x;
    }
    bool join(int a,int b){
        a=find(a);
        b=find(b);
        if(a==b){
            return false;
        }
        if(size[a]<size[b]){
            swap(a,b);
        }
        parent[b]=a;
        size[a]+=size[b];
        return true;
    }
};
int main(){
    // Compute the exact archive answer using the method explained above.
    for(int test=0;test<2;test++){
        int n;
        cin>>n;
        DSU dsu(n);
        int components=n;
        for(int i=0;i<n;i++){
            int location;
            cin>>location;
            if(dsu.join(i,location-1)){
                components--;
            }
        }
        if(test!=0){
            cout<<' ';
        }
        cout<<components;
    }
    cout<<'\n';
}