NAQ22 G Solution (C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>

using namespace std;

///// COPIED FROM NOTES
int n;
vector<vector<int>> adj;
vector<vector<int>> adj_t;
vector<bool> vis;
vector<int> comp;
vector<int> order;
long long mod = 1e9+7;

void visit(int u)
{
    vis[u] = true;
    for(int v:adj[u]) if(!vis[v]) visit(v);
    order.push_back(u);
}

void assign(int u, int k)
{
    comp[u] = k;
    for(int v:adj_t[u]) if(comp[v]==-1) assign(v, k);
}

void scc()
{
    adj_t.resize(n);
    for(int u=0;u<n;u++) for(int v:adj[u]) adj_t[v].push_back(u);

    vis.resize(n);
    for(int u=0;u<n;u++) if(!vis[u]) visit(u);
    reverse(order.begin(), order.end());

    comp.assign(n, -1);
    int curr = 0;
    for(int u:order) if(comp[u]==-1) assign(u, curr++);
}
//////////////////////////////////////////////////////////

// calculate number of variants ending at a node c
// given the transposed condensation graph
long long cont(vector<set<int>>& hg_t, int c)
{
    if(hg_t[c].size()==0) return 1;

    long long pp = 1;
    for(int p:hg_t[c])
    {
        pp = (pp * ( (cont(hg_t, p) + 1) % mod) % mod) % mod;
    }

    // i went overkill on the mods
    return pp % mod;
}

int main()
{
    // build the initial graph
    cin>>n;
    adj.assign(n, vector<int>(0));
    for(int u=0;u<n;u++)
    {
        int v;
        cin>>v;
        v--;
        adj[u].push_back(v);
    }

    // run scc
    scc();

    // maps scc id to the nodes in that scc
    map<int,vector<int>> ctn;
    for(int i=0;i<n;i++) ctn[comp[i]].push_back(i);

    // build the condensation graph
    // by checking for scc adjacency to other scc's
    int n_comps = ctn.size();
    vector<set<int>> hg;
    hg.resize(n_comps);

    for(int c=0;c<n_comps;c++)
    {
        for(int u:ctn[c])
            for(int v:adj[u])
                if(comp[v]!=c) hg[c].insert(comp[v]);
    }


    // find the sinks of the condensation graph
    set<int> sinks;
    for(int c=0;c<n_comps;c++) if(hg[c].size()==0) sinks.insert(c);


    // build transposed condensation graph
    vector<set<int>> hg_t(n_comps);
    for(int c=0;c<n_comps;c++)
    {
        for(int k:hg[c]) hg_t[k].insert(c);
    }

    // calculate answer
    long long ans = 1;
    for(int sink : sinks)
    {
        ans =  (ans * ( cont(hg_t, sink) + 1 ) % mod ) % mod; //(ans + (fast_pow(2, n_sinks-1) * cont(hg_t, sink)) % mod) % mod;
    }

    // subtracting 1 to disclude empty set
    ans = (mod + ans - 1) % mod;

    cout << ans << '\n';
}