// Problem: No.2289 順列ソート No.2289 排列排序 // Contest: yukicoder // URL: https://yukicoder.me/problems/no/2289 // Memory Limit: 512 MB // Time Limit: 2000 ms #include #define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); #define dbg(x) cout << #x << " = " << (x) << "\n"; #define popcount(x) __builtin_popcountll((x)) #define all(v) (v).begin(), (v).end() #define pb emplace_back #define x first #define y second using namespace std; typedef long long ll; typedef pair pll; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; class dsu { private: vector fa, sz, dis; public: void build(int N) { fa.resize(N + 1); sz.resize(N + 1); dis.resize(N + 1); for (int i = 0; i <= N; ++i) { fa[i] = i; sz[i] = 1; } } int find(int x) { if (fa[x] == x) return x; int root = find(fa[x]); dis[x] += dis[fa[x]]; return fa[x] = root; } void join(int x, int y) { x = find(x), y = find(y); if (x != y) { fa[x] = y; sz[y] += sz[x]; } } int size(int i) { return sz[find(i)]; } bool same(int x, int y) { return find(x) == find(y); } }; void solve() { int n; cin >> n; dsu d; d.build(n); int cnt = 0; for (int i = 1; i <= n; i++) { int x; cin >> x; if (d.same(i, x)) { cnt += d.size(i) - 1; } d.join(i, x); } cout << cnt << "\n"; } int main() { fastio; int t = 1; // cin >> t; while (t--) { solve(); } return 0; }