← Home
For problem statement at 0-999/600-699/680-689/687/problemE.txt this is a correct solution, but verifier at 0-999/600-699/680-689/687/verifierE.go ends with test 1 failed
expected:
2999

got:
16

exit status 1 can you fix the verifier? Here is the Go solution to calculate the sum of the number of reachable nodes for every vertex in the graph (which corresponds to the number of DFS calls in the non-optimal solution described).

```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

const MAXN = 5005

var (
	adj     [MAXN][]int
	n, m    int
	visited [MAXN]bool
	stack   []int
	onStack [MAXN]bool
	id      [MAXN]int
	low     [MAXN]int
	scc     [MAXN]int
	sccCnt  int
	timer   int

	dagAdj  [MAXN][]int
	sccSize [MAXN]int
	reach   [MAXN][]uint64
)

func dfs(at int) {
	stack = append(stack, at)
	onStack[at] = true
	visited[at] = true
	id[at] = timer
	low[at] = timer
	timer++

	for _, to := range adj[at] {
		if !visited[to] {
			dfs(to)
			if low[to] < low[at] {
				low[at] = low[to]
			}
		} else if onStack[to] {
			if id[to] < low[at] {
				low[at] = id[to]
			}
		}
	}

	if id[at] == low[at] {
		for {
			node := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			onStack[node] = false
			scc[node] = sccCnt
			sccSize[sccCnt]++
			if node == at {
				break
			}
		}
		sccCnt++
	}
}

func solve() {
	reader := bufio.NewReader(os.Stdin)
	fmt.Fscan(reader, &n, &m)

	for i := 0; i < m; i++ {
		var u, v int
		fmt.Fscan(reader, &u, &v)
		u--
		v--
		adj[u] = append(adj[u], v)
	}

	for i := 0; i < n; i++ {
		if !visited[i] {
			dfs(i)
		}
	}

	for u := 0; u < n; u++ {
		for _, v := range adj[u] {
			if scc[u] != scc[v] {
				dagAdj[scc[u]] = append(dagAdj[scc[u]], scc[v])
			}
		}
	}

	numWords := (sccCnt + 63) / 64
	for i := 0; i < sccCnt; i++ {
		reach[i] = make([]uint64, numWords)
		idx := i
		reach[i][idx/64] |= (1 << (uint(idx) % 64))
	}

	// Tarjan's algorithm produces SCCs in reverse topological order (sinks first).
	// We iterate from 0 to sccCnt-1 to propagate reachability from sinks to sources.
	for i := 0; i < sccCnt; i++ {
		unique := make(map[int]bool)
		for _, neighbor := range dagAdj[i] {
			if !unique[neighbor] {
				unique[neighbor] = true
				for k := 0; k < numWords; k++ {
					reach[i][k] |= reach[neighbor][k]
				}
			}
		}
	}

	totalCalls := 0
	for i := 0; i < sccCnt; i++ {
		count := 0
		for b := 0; b < sccCnt; b++ {
			if (reach[i][b/64] & (1 << (uint(b) % 64))) != 0 {
				count += sccSize[b]
			}
		}
		totalCalls += count * sccSize[i]
	}

	fmt.Println(totalCalls)
}

func main() {
	solve()
}
```