As far as I know the question of "is it possible to solve that faster than quadratic time" is an open problem.

You can optimize $$$O(n^2)$$$ with bitsets. If doing straightforward, this probably will give MLE (if n = $$$10^5$$$, ML = 256/512MB), but you can try to divide all vertices on groups, and for each group G runs separate dfs: for each vertex V count how many of vertices U(from G) are reachable from V.

Spoj Problem DAGCNT2 is similar to this

This can be done by first finding Strongly Connected Components (SCC), which can be done in O(|V|+|E|). Then, build a new graph, G', where each SCC is a node in the graph and each node has value which is the sum of the nodes in that SCC.

Given a graph G(V, E), we build G'(V', E') where:

V' = { U1, U2, ..., Uk | U_i is a SCC of the graph G }

E' = { (U, W) | there is node u in U and w in W such that (u, w) is in E }

This graph, G', is a DAG and the question becomes similar with finding the number of nodes reachable from each node in a DAG, which can be made easily via DFS:

int DFS(node v) {
    vis[v] = true
    reachable[v] = v.scc_size() // nodes reachable from that SCC, including themselves

    for u in v.children() {
        // nodes already visited were added via previously visited nodes
        if (vis[u] == false) {
            reachable[v] += DFS(u)
        }
    }

    return reachable[v]
}

for v in V'  '{
    if (indegree(v) == 0) {
        DFS(v)
    }
}

So for the original nodes from G we get very easily the number of reachable nodes:

for v in V {
    reachable_G[v] = reachable[containing_scc(v)]
}

Thus the final complexity is linear O(|V| + |E|) .

Basically for every node it will be n^2. So total time complexity becomes n^3 right? @author