Shortest paths - interesting graph problems
You are given an acyclic directed graph, consisting of n nodes and k edges. Find the number of edges in its transitive closure.
Transitive closure of graph G is a graph G', consisting of all nodes of original graph G and such edges (u, v) that there is a path from node u to v in graph G.
Knuth knows how to solve the problem. And what about you?
The first line contains two numbers n and k (1 ≤ n, k ≤ 50000). Then k lines follow, each containing two integers
bi, describing directed edge from
bi (1 ≤
bi ≤ n). Graph doesn't contain loops, cycles and multiple edges.
Print the number of edges in transitive closure.
5 6 1 2 2 3 3 5 4 5 1 5 1 3