favorite We need a little bit of your help to keep things running, click on this banner to learn more

Shortest paths - interesting graph problems

K-edges graph

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 (1n, k50000). Then k lines follow, each containing two integers ai and bi, describing directed edge from ai to bi (1ai, bin). Graph doesn't contain loops, cycles and multiple edges.


Print the number of edges in transitive closure.

Time limit 2 seconds
Memory limit 512 MiB
Input example #1
5 6
1 2
2 3
3 5
4 5
1 5
1 3
Output example #1
Author А. Milanin
Source 2013 Winter School Kharkov, Day 1, Problem K