HackerEarth Choose but not both problem solution

In this HackerEarth Choose but not both problem solution The alone Y has another array a1,a2,...,an that 1<=ai<=n. this time Y wants to choose some numbers from 1 to n that there is no i that both i and ai is chosen.

What is the maximum amount of numbers that Y can choose?

HackerEarth Choose but not both problem solution.

#include<bits/stdc++.h>

using namespace std;

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

const int N = 3e5+100;

int f[N];
bool mark[N], mark2[N];
vector<int> r[N];

ii dfs(int v){
    mark[v] = true;
    ii ret = ii(1, 0);
    for(auto u : r[v]){
        if(!mark[u]){
            ii cur = dfs(u);
            ret.second += max(cur.first, cur.second);
            ret.first += cur.second;
        }
    }
    return ret;
}

int solve_linear(vector<ii> v){
    int ls[2] = {0, 0};
    for(auto i : v){
        ls[1] += i.second;
        ls[0] += max(i.first, i.second);
        swap(ls[0], ls[1]);
    }
    return max(ls[0], ls[1]);
}

int solve(vector<int> cyc){
    for(auto i : cyc)
        mark[i] = true;
    vector<ii> v;
    for(auto i : cyc)
        v.push_back(dfs(i));

    if(v.size() == 1)
        return v[0].second;

    if(v.size() == 2){
        int ret = v[0].first + v[1].second;
        ret = max(ret, v[0].second + v[1].first);
        ret = max(ret, v[0].second + v[1].second);
        return ret;
    }

    // 1 is chosen
    int ret = [&]{
        vector<ii> cur;
        for(int i=3 ; i<v.size() ; i++)
            cur.push_back(v[i]);
        return max(v[1].first, v[1].second) + v[0].second + v[2].second + solve_linear(cur);
    }();

    // 1 is not chosen
    ret = max(ret, [&]{
        vector<ii> cur;
        for(int i=2 ; i<v.size() ; i++)
            cur.push_back(v[i]);
        cur.push_back(v[0]);
        return v[1].second + solve_linear(cur);
    }());

    return ret;
}

signed main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int n;cin >> n;
    for(int i=0 ; i<n ; i++){
        cin >> f[i];f[i] --;
        r[ f[i] ].push_back(i);
    }

    int ans=0;

    for(int i=0 ; i<n ; i++){
        if(mark[i])
            continue;
        // finding cycle
        auto cyc = [&]{ 
            vector<int> cyc;
            int it = i;
            while(!mark2[it]){
                mark2[it] = true;
                cyc.push_back(it);
                it = f[it];
            }
            reverse(cyc.begin(), cyc.end());
            while(cyc.back() != it)
                cyc.pop_back();
            return cyc;
        }();
        ans += solve(cyc);
    }

    cout << ans << "\n";
}