# 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";}`